С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 29
Текст из файла (страница 29)
Исходя из вычислительных формул (.) и принимая во внимание (.), (.), мы заключаем, что битовые затраты, дополнительные к затратам собственно алгоритма Евклида («нерасширенного») на вычисление sn , tn , допускают оценкуO(log a0 log a1 ) — это обосновывается так же, как оценка (.). Поэтому сложность добавочной части расширенного алгоритма Евклида допускает оценку O(log2 a0 ) и, в силу теоремы ., оценку O(m2 ).Остается заметить, что, например, Θ(m2 ) + O(m2 ) = Θ(m2 ).§ . Модулярная арифметика§ . Модулярная арифметикаМногие арифметические алгоритмы основываются на вычисленияхпо некоторому целому модулю k, или, как говорят, на модулярныхвычислениях; соответственно, говорят о модулярной арифметике.
Далее в этом параграфе мы считаем k фиксированным целым положительным числом.Целые a и b называют сравнимыми по модулю k и пишутa ≡ b (mod k),(.)если k | (a − b), т. е. если k является делителем разности a − b. Соотношение вида (.) называется сравнением. Изложение основ теориисравнений можно найти в любом учебнике алгебры . Мы приведемосновные элементарные факты этой теории, не останавливаясь на ихдоказательстве:(i) бинарное отношение сравнимости по модулю k является отношением эквивалентности на множестве целых чисел Z;(ii) еслиa1 ≡ b1 (mod k) и a2 ≡ b2 (mod k),тоa1 ± a2 ≡ b1 ± b2 (mod k) и a1 a2 ≡ b1 b2 (mod k);(iii) каждое целое число a сравнимо по модулю k в точности с одним целым числом из множества {0, 1, ..., k − 1}.В силу (i) множество Z разбивается на классы эквивалентности помодулю k (кратко: классы по модулю k), и, согласно (ii), эти классыобразуют кольцо, если считать, что сумма двух классов — это класс,содержащий сумму каких-либо чисел, взятых по одному из складываемых классов, а произведение — это, соответственно, класс, содержащий произведение каких-либо чисел, взятых по одному из перемножаемых классов.
Нулем этого кольца является класс, содержащийчисло 0. Для введенного кольца используется обозначение Zk , его называют кольцом вычетов по модулю k (вычет — это в данном случаедругое название класса эквивалентности по модулю k).Любое множество {a0 , a1 , ..., ak−1 } чисел, взятых по одному из каждого класса по модулю k, называется полной системой представителей по модулю k.МножествоIk = {0, 1, ..., k − 1},См., например, [, § , ] и [, гл. , § , п. ].Глава .
Битовая сложностьуказанное в (iii), называется канонической (или начальной) полнойсистемой представителей по модулю k. Иногда используется и симметричная полная система представителей:mj konlk−k + 1, ..., −1, 0, 1, ...,,Sk =22которая является симметричной (при условии игнорирования знаков) только при нечетном k: например, S3 = {−1, 0, 1} и S4 == {−1, 0, 1, 2}.Пусть для изображения элементов кольца Zk используется система Ik . Операциям сложения и умножения в Zk соответствуют обычные сложение и умножение в Z с последующей заменой полученногорезультата остатком от его деления на k. Если некоторому элементу кольца Zk соответствует число a системы Ik , то противоположному (обратному по сложению) элементу будет соответствовать числоk − a, если a 6= 0, и число 0, если a = 0.Исследуем битовую сложность операций в кольце Zk .
Будем считать размером входа битовую длину m числа k и ограничимся верхними асимптотическими оценками. Для операций сложения и нахождения противоположной величины имеем, очевидно, оценку O(m). Использование операции наивного умножения целых чисел приводитк оценке O(m2 ) для сложности умножения в Zk . Эта оценка, разумеется, сохраняется и при использовании более быстрого умноженияи деления в Z.Как известно, в случае простого k кольцо Zk является полем.
Присоставном k это кольцо полем не является и, более того, содержит делители нуля: если k = pq, p > 1, q > 1, то произведение элементов Zk ,изображаемых числами p, q ∈ Ik , равно нулю. Допустим, что k является простым и примем для этого простого числа обозначение p,по-прежнему считая его битовую длину равной m. Нахождение обратного к элементу кольца Z p , представленному целым ненулевымчислом a ∈ I p , может быть выполнено с помощью расширенного алгоритма Евклида.
Так как p и a, очевидно, взаимно просты, то c помощью расширенного алгоритма Евклида можно найти s и t такие, чтоsp + ta = 1. Получаем ta ≡ 1 (mod p), т. е. обратным к классу, содержащему a, является класс, содержащий t. В силу (.) имеем | t | < p;если t < 0, то заменяем t на t + p (напомним, что мы используемэлементы системы I p для изображения элементов поля Z p ).Пример ..
Для p = 13, a = 5 получаем с помощью расширенногоалгоритма Евклида 2 · 13 + (−5) · 5 = 1, и отсюда 8 = −5 + 13 являетсяобратным для 5 в Z13 (проверка подтверждает это: 5 · 8 ≡ 1 (mod 13)).§ . Модулярная арифметикаКак следствие предложения . получаем такое утверждение.Предложение .. Пусть расширенный алгоритм Евклида основывается на некоторых алгоритмах деления с остатком и умножения, битовые затраты каждого из которых применительно к целымv и w допускают оценку O(log v log w). Тогда битовая сложность обращения в поле Z p с помощью расширенного алгоритма Евклида допускает оценку O(log2 p) при использовании числа p в качестве размеравхода и, соответственно, оценку O(m2 ) при использовании в этомкачестве битовой длины m числа p.Несомненным достоинством алгоритма обращения, основанногона расширенном алгоритме Евклида, состоит в том, что с его помощью обращение возможно всякий раз, когда обращаемое число и модуль взаимно просты, а не только тогда, когда модуль — простое число.
Например, можно определить a такое, что 5a ≡ 1 (mod 6) — средичисел, входящих в I6 , значением a является 5. В этом смысле применимость этого алгоритма шире, чем, например, алгоритма, основанного на малой теореме Ферма.Малая теорема Ферма. Пусть p — простое число, a — произвольное целое. Тогда a p ≡ a (mod p).(Путь доказательства показан в задаче .) Если a не делится на p,то согласно этой теореме a p−2 является обратным к a по простомумодулю p. Но это, вообще говоря, неверно для составных p. Например, неверно, что 55 ≡ 1 (mod 6).С помощью расширенного алгоритма Евклида возможно обращениепо модулю k любого числа a, взаимно простого с k; если a ∈ Ik илиa ∈ Sk , то это обращение имеет битовую сложность O(log2 k) илиO(m2 ), коль скоро в качестве размера входа используется m = λ(k).Пример ..
Уже говорилось, что вопрос о возможности распознавания простоты со сложностью O(md ) с некоторым d ∈ N представляет большой интерес и что, скажем, алгоритм пробных делений(примеры ., ., .) не обладает указанным свойством даже прирассмотрении не битовой сложности, а сложности по числу делений,причем как в худшем случае, так и в среднем.Если для некоторого a ∈ Z, не делящегося на n, мы обнаружим,что не выполняется сравнениеan ≡ a (mod n),(.)Глава .
Битовая сложностьто по малой теореме Ферма из этого можно заключить, что n неявляется простым. Если фиксировано число a такое, что 1 < a < n,то использование бинарного алгоритма возведения в степень с заменой результата каждого из умножений остатком от деления на nпозволяет вычислить an и проверить выполнение сравнения (.),затратив O(log3 n), или, что то же самое, O(m3 ) битовых операций,где m = λ(n). Однако это не позволяет утверждать, что мы можемна основе этого распознавать простоту n за O(m3 ) битовых операций, так как существует бесконечно много составных n таких, что(.) выполняется для любых a, взаимно простых с n.
Это так называемые числа Кармайкла (наименьшее из которых равно 561 == 3 · 11 · 17).Напомним, что алгоритм со сложностью O(md ), где m — размервхода, d ∈ N, называют алгоритмом с полиномиально ограниченнойсложностью или полиномиальным. В задаче распознавания простотычисла за размер входа берется количество m двоичных цифр числа nили же log2 n. После долгих поисков, в которых принимали участиеразные исследователи, алгоритм с полиномиально ограниченной битовой сложностью был в г. предложен тремя индийскими математиками — М. Агравалом, H. Кайалом и H. Саксеной . Этот алгоритмполучил в литературе название AKS по первым буквам фамилий авторов.
Мы обсудим лишь главную идею алгоритма AKS, основаниемкоторого служит следующее необходимое и достаточное условие простоты числа n.Предложение .. Пусть a ∈ Z, n ∈ N взаимно просты, тогдаn является простым, если и только если выполнено полиномиальноесравнение(x − a)n ≡ x n − a (mod n),(.)которое надо понимать так, что числовые коэффициенты при одинаковых степенях x в полиномах, расположенных в левой и правойчастях, сравнимы по модулю n.Доказательство.
Пусть n — простое. Если n = 2, то выполнение(.) проверяется непосредственно, и остается рассмотреть случайнечетного n. Коэффициенты при x k в левой и правой частях дляk nслучая 1 < k < n равны соответственно (−1)an−k и 0. При этомk nделится на n, так как n простое (см. задачу ).
Коэффициентыkпри x n в обеих частях (.) равны 1, свободные члены соответственСм. [].§ . Модулярная арифметикано равны (−a)n и −a. В силу нечетности n достаточно показать, чтоan ≡ a (mod n), а это сравнение выполняется в силу малой теоремыФерма. Мы доказали, что если n — простое, то выполнено (.).Пусть теперь n — составное. Пусть, далее, простое q и l ∈ N+ таковы, что q l | n и при этом неверно, что q l +1 | n. Имеем (n − q + 1)(n − q + 2)...nn.=q!qТак как q | n, то произведение (n − q + 1)(n − q + 2)...(n − 1) не делится на q; при этом один из входящих в n множителей, равных q, сокраnтится со знаменателем. Поэтомуне делится на q l .
Помимо этого,qq l взаимно просто с an−q , так как a и q взаимно просты. Поэтому коqn− q n− q nэффициент при x в левой части (.), равный (−1) a, неqделится на q l , следовательно, не делится на n и поэтому не сравнимс по модулю n. Мы доказали, что если n — составное, то сравнение (.) не имеет места.Из предложения . следует, что для проверки простоты числа nможно взять любое a, взаимно простое с n (подходит, например, ),и проверить (.).
Но прямая такая проверка потребует Ω(n) = Ω(2m )битовых операций, так как раскрытие скобок в левой части (.)дает n + 1 слагаемое. Алгоритм AKS предписывает проверку (.)по двум модулям(x − a)n ≡ x n − a (mod x r − 1, n),(.)r > 0. Сравнение (.) понимается в том смысле, что все коэффициенты остатка от деления полинома (x − a)n − x n + a на x r − 1 (онибудут целыми числами) делятся на n. Вычисление остатков от деления (x − a)n и x n на x r − 1 производится с помощью бинарного алгоритма возведения в степень, результат каждого умножения сразуже заменяется остатком от деления на x r − 1. Но если взять произвольное r ∈ N+ , то может оказаться, что (.) выполняется и принекоторых составных n. Число r должно подбираться специальнымобразом, и авторы показывают, что подходящее для целей алгоритма r всегда существует и может быть выбрано без существенных затрат так, что r = O(m5 ); после выбора r сравнение (.) надо проверить для «небольшого»числа «легко определяемых» a — количествоpэтих a есть O( rm).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
