Глава 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. Модулярная арифметика

147

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

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

Несомненным достоинством алгоритма обращения, основанного на расширенном алгоритме Евклида, состоит в том, что с его помо­щью обращение возможно всякий раз, когда обращаемое число и мо­дуль взаимно просты, а не только тогда, когда модуль—простое чис­ло. Например, можно определить a такое, что 5a = 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) не обладает указанным свойством даже при рассмотрении не битовой сложности, а сложности по числу делений, причем как в худшем случае, так и в среднем.

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

aⁿ ≡ a (mod n),

(22.2)

148