Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 31
Текст из файла (страница 31)
В этом смысле применимость этого алгоритма шире, чем, например, алгоритма, основанного на малой теореме Ферма.Малая теорема Ферма. Пусть 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).
Итоговая сложность алгоритма допускает оценку O(m11 ). Заметим попутно, что в литературе по теории сложностиe f (m)) (Oe называется «O мягкое»),часто используются оценки вида O(Глава . Битовая сложностьза таким обозначением скрывается O( f (m) logd m), где d — положительное число, значение которого не уточняется. Авторы показывают,e 21/2 ), укачто битовая сложность их алгоритма допускает оценку O(mзывая при этом, что если верны некоторые известные в теории чиселгипотезы (для которых имеются серьезные основания полагать, чтоони верны), то можно взять r = O(m2 ), и в этом случае сложностьe 6 ).алгоритма в целом есть O(mНа этом мы завершим разговор об алгоритме AKS, добавив лишько всему сказанному, что, например, в криптографии практикуютсявероятностные (типа Монте-Карло) алгоритмы распознавания простоты, имеющие меньшую сложность, но не исключающие появления, хоть и с малой вероятностью, неверного ответа.
В нашем курсетакого рода алгоритмы не рассматриваются .§ . Булева арифметикаСложность булевых вычислений как сложность по числу булевых операций может рассматриваться как алгебраическая сложность. Но работа с булевыми величинами является фактически работой с битами, и сложность по числу булевых операций в этом смысле совпадает с битовой сложностью. Таким образом, для алгоритмов булевойарифметики алгебраическая сложность по числу булевых операцийи битовая сложность — это одно и то же. Аналогично дело обстоити с пространственной булевой (= битовой) сложностью.Пример .. Пусть дан ориентированный граф G = (V , E), n = | V |.Пусть C = (cij ) — булева матрица смежности графа G: cij = 1, еслии только если i-я вершина соединена ребром с j-й, i, j = 1, 2, ..., n.Требуется построить для G его матрицу связности D = (dij ): dij = 1,если и только если i = j или i-я вершина соединена путем из одногоили более ребер с j-й, i, j = 1, 2, ..., n.
Если рассматривать G как графнекоторого бинарного отношения на множестве из n элементов, тозадачу можно интерпретировать как задачу построения транзитивно-рефлексивного замыкания данного бинарного отношения. Соответственно, граф, для которого D является матрицей смежности, называют транзитивно-рефлексивным замыканием графа G, а саму матрицу D — транзитивно-рефлексивным замыканием матрицы C. Дляматрицы D используется обозначение C ∗ . На рис.
показан ориентированный граф и его транзитивно-рефлексивное замыкание. СоотПо поводу этих алгоритмов распознавания простоты числа см. [, гл. ] и [,гл. ].§ . Булева арифметика43а)4312б)1525Рис. . а) Ориентированный граф; б) его транзитивно-рефлексивное замыкание.и C ∗ выглядят следующим образом1 1 1 10 11 01 1 1 1. , C∗ = 0 11 1 1 10 0 0 10 0ветствующие матрицы C0 10 1C =1 00 0Нам понадобятся произведения булевых матриц, которые определяются как обычно: например, произведение F квадратных матрицA и B порядка n определяется формулойfij =n_(aik ∧ bkj ),i, j = 1, 2, ..., n.k =1Элемент с индексами i, j для краткости будем называть (i, j)-элементом матрицы.Легко видеть, что C 2 = C ∧ C — это матрица, для которой (i, j)-элемент равен 1, если и только если i-я вершина соединена с j-й путемдлины 2 (т.
е. состоящим из двух ребер). Аналогично, C k — матрица,для которой (i, j)-элемент равен 1, если и только если i-я вершина соединена с j-й путем длины k. Пусть I — матрица, для которой(i, j)-элемент равен 1, если и только если i = j. ТогдаC ∗ = I ∨ C ∨ C 2 ∨ ... ∨ C n−1 .Индукцией по k несложно доказать, что для любой квадратной булевой матрицы C и натурального k выполненоI ∨ C ∨ C 2 ∨ ... ∨ C k = (I ∨ C)k .(.)C ∗ = (I ∨ C)n−1 .(.)Это дает намГлава . Битовая сложностьТривиальный способ умножения булевых (n × n)-матрицΘ(n3 ) битовых операций.