Модулярная арифметика

Многие арифметические алгоритмы основываются на вычислениях по некоторому целому модулю k, или, как говорят, на модулярных вычислениях; соответственно, говорят о модулярной арифметике. Да­лее в этом параграфе мы считаем k фиксированным целым положи­тельным числом.

Целые a и b называют сравнимыми по модулю k и пишут

a ≡ b (mod k), (22.1)

если k | (a - b), т. е. если k является делителем разности a - b. Соот­ношение вида (22.1) называется сравнением. Изложение основ теории сравнений можно найти в любом учебнике алгебры¹. Мы приведем основные элементарные факты этой теории, не останавливаясь на их доказательстве:

(i) бинарное отношение сравнимости по модулю k является от­ношением эквивалентности на множестве целых чисел Z; (ii) если

a _г ≡ b _г (mod k) и a₂ ≡ b₂ (mod k), то

a_г±a₂ ≡ b_г± b₂ (mod k) и a_гa₂ ≡ b_гb₂ (mod k);

(iii) каждое целое число a сравнимо по модулю k в точности с од­ним целым числом из множества {О,1,..., k - 1}.

В силу (i) множество Z разбивается на классы эквивалентности по модулю k (кратко: классы по модулю k), и, согласно (ii), эти классы образуют кольцо, если считать, что сумма двух классов — это класс, содержащий сумму каких-либо чисел, взятых по одному из склады­ваемых классов, а произведение — это, соответственно, класс, содер­жащий произведение каких-либо чисел, взятых по одному из пере­множаемых классов. Нулем этого кольца является класс, содержащий число 0. Для введенного кольца используется обозначение Z_k, его на­зывают кольцом вычетов по модулю k (вычет—это в данном случае другое название класса эквивалентности по модулю k).

Любое множество {a₀, a _ъ ■■■,a_k-₁} чисел, взятых по одному из каж­дого класса по модулю k, называется полной системой представите­лей по модулю k.

Множество

I _k = {0,1,... k -1},

См., например, [14, § 42, 43] и [22, гл. 4, § 4, п. 2].

Глава 5. Битовая сложность

указанное в (iii), называется канонической (или начальной) полной системой представителей по модулю к. Иногда используется и сим­метричная полная система представителей:

§_fc = jr_-Ltil..,-1,0,1,..., UJ},

которая является симметричной (при условии игнорирования зна­ков) только при нечетном к: например, §₃ = {-1>0>1} и §₄ = = {-1,0,1,2}.

Пусть для изображения элементов кольца Z_fc используется систе­ма 1_к. Операциям сложения и умножения в Z_k соответствуют обыч­ные сложение и умножение в Z с последующей заменой полученного результата остатком от его деления на к. Если некоторому элемен­ту кольца Z_k соответствует число а системы 1_к, то противоположно­му (обратному по сложению) элементу будет соответствовать число к - а, если а Ф 0, и число 0, если а = 0.

Исследуем битовую сложность операций в кольце Z_fc. Будем счи­тать размером входа битовую длину т числа к и ограничимся верхни­ми асимптотическими оценками. Для операций сложения и нахожде­ния противоположной величины имеем, очевидно, оценку 0(т). Ис­пользование операции наивного умножения целых чисел приводит к оценке 0{т²) для сложности умножения в Z_k. Эта оценка, разуме­ется, сохраняется и при использовании более быстрого умножения и деления в Z.

Как известно, в случае простого к кольцо Z_fc является полем. При составном к это кольцо полем не является и, более того, содержит де­лители нуля: если к = pq, р > 1, q > 1, то произведение элементов Z_fc, изображаемых числами р, q е 1_к, равно нулю. Допустим, что к явля­ется простым и примем для этого простого числа обозначение р, по-прежнему считая его битовую длину равной т. Нахождение об­ратного к элементу кольца Z _p, представленному целым ненулевым числом а&1_р, может быть выполнено с помощью расширенного ал­горитма Евклида. Так как р и а, очевидно, взаимно просты, то c помо­щью расширенного алгоритма Евклида можно найти s и t такие, что sp + ta = l. Получаем ta = l (mod р), т.е. обратным к классу, содер­жащему а, является класс, содержащий t. В силу (9.13) имеем \t\<p; если t < 0, то заменяем t на t + р (напомним, что мы используем элементы системы 1_р для изображения элементов поля Z _p).

Пример 22.1. Для р = 13, а = 5 получаем с помощью расширенного алгоритма Евклида 2 • 13 + (-5) • 5 = 1, и отсюда 8 = -5 + 13 является обратным для 5 в Z₁₃ (проверка подтверждает это: 5-8 = 1 (mod 13)).

§ 22. Модулярная арифметика

Как следствие предложения 21.3 получаем такое утверждение.

Предложение 22.1. Пусть расширенный алгоритм Евклида осно­вывается на некоторых алгоритмах деления с остатком и умноже­ния, битовые затраты каждого из которых применительно к целым v иw допускают оценку O (log v log w). Тогда битовая сложность об­ращения в поле Z_p с помощью расширенного алгоритма Евклида допус­кает оценку O (log² p) при использовании числа p в качестве размера входа и, соответственно, оценку O(m²) при использовании в этом качестве битовой длины m числа p.

Несомненным достоинством алгоритма обращения, основанного на расширенном алгоритме Евклида, состоит в том, что с его помо­щью обращение возможно всякий раз, когда обращаемое число и мо­дуль взаимно просты, а не только тогда, когда модуль—простое чис­ло. Например, можно определить a такое, что 5 a = 1 (mod 6)—среди чисел, входящих в 1₆, значением a является 5. В этом смысле приме­нимость этого алгоритма шире, чем, например, алгоритма, основан­ного на малой теореме Ферма.

Малая теорема Ферма. Пусть p — простое число, a — произволь­ное целое. Тогда a^p=a (mod p).

(Путь доказательства показан в задаче 108.) Если a не делится на p, то согласно этой теореме a^p~² является обратным к a по простому модулю p. Но это, вообще говоря, неверно для составных p. Напри­мер, неверно, что 5⁵ = 1 (mod 6).

С помощью расширенного алгоритма Евклида возможно обращение по модулю k любого числа a, взаимно простого с k; если a е1 _k или a е§ _k, то это обращение имеет битовую сложность O (teg² k) или O(m²), коль скоро в качестве размера входа используется m = A(k).

Пример 22.2. Уже говорилось, что вопрос о возможности распо­знавания простоты со сложностью O{m^d) с некоторым d е N пред­ставляет большой интерес и что, скажем, алгоритм пробных делений (примеры 1.2, 4.1, 5.2) не обладает указанным свойством даже при рассмотрении не битовой сложности, а сложности по числу делений, причем как в худшем случае, так и в среднем.

Если для некоторого a eZ, не делящегося на n, мы обнаружим, что не выполняется сравнение

aⁿ ≡ a (mod n),

(22.2)

Глава 5. Битовая сложность

то по малой теореме Ферма из этого можно заключить, что n не является простым. Если фиксировано число a такое, что 1 < a < n, то использование бинарного алгоритма возведения в степень с за­меной результата каждого из умножений остатком от деления на n позволяет вычислить aⁿ и проверить выполнение сравнения (22.2), затратив O (log³ n), или, что то же самое, O(m^ъ) битовых операций, где m = A(n). Однако это не позволяет утверждать, что мы можем на основе этого распознавать простоту n за O{m?) битовых опера­ций, так как существует бесконечно много составных n таких, что

(22.2) выполняется для любых a, взаимно простых с n. Это так на­
зываемые числа Кармайкла (наименьшее из которых равно 561 =
= 3-11 • 17).

Напомним, что алгоритм со сложностью O{m^d), где m — размер входа, d е N, называют алгоритмом с полиномиально ограниченной сложностью или полиномиальным. В задаче распознавания простоты числа за размер входа берется количество m двоичных цифр числа n или же log₂ n. После долгих поисков, в которых принимали участие разные исследователи, алгоритм с полиномиально ограниченной би­товой сложностью был в 2002 г. предложен тремя индийскими мате­матиками— М. Агравалом, H. Кайалом и H. Саксеной¹. Этот алгоритм получил в литературе название AKS по первым буквам фамилий ав­торов. Мы обсудим лишь главную идею алгоритма AKS, основанием которого служит следующее необходимое и достаточное условие про­стоты числа n.

Предложение 22.2. Пусть a е Z, n eN взаимно просты, тогда n является простым, если и только если выполнено полиномиальное сравнение

(x - a) n = xⁿ - a (mod n), (22.3)

которое надо понимать так, что числовые коэффициенты при оди­наковых степенях x в полиномах, расположенных в левой и правой частях, сравнимы по модулю n.

Доказательство. Пусть n —простое. Если n = 2, то выполнение

(22.3) проверяется непосредственно, и остается рассмотреть случай
нечетного n. Коэффициенты при x^k в левой и правой частях для

случая 1 < k < n равны соответственно и 0. При этом

(_k) делится на n, так как n простое (см. задачу 107). Коэффициенты при xⁿ в обеих частях (22.3) равны 1, свободные члены соответствен­См. [42].

§ 22. Модулярная арифметика

но равны (-а)" и -а. В силу нечетности п достаточно показать, что а^п = а (mod п), а это сравнение выполняется в силу малой теоремы Ферма. Мы доказали, что если п — простое, то выполнено (22.3).

Пусть теперь п — составное. Пусть, далее, простое q и ZeN⁺ тако­вы, что q^l | п и при этом неверно, что q^l+1 | п. Имеем

ГпЛ (n - q + l)(n - q + 2)... n

q q!

Так как q | п, то произведение (п - q + 1)(п - q + 2)... (п - 1) не делит­ся на q; при этом один из входящих в п множителей, равных q, сокра­тится со знаменателем. Поэтому (^п ] не делится на q^l. Помимо этого,

Дата добавления: 2014-01-11