Глава 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, neN взаимно просты, тогда 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. Модулярная арифметика

149

но равны (-а)" и -а. В силу нечетности п достаточно показать, что а^п = а (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. Помимо этого,

g

q^l взаимно просто с а"-^ч, так как а и q взаимно просты. Поэтому ко­эффициент при х" в левой части (22.3), равный (-l)ⁿ-^qaⁿ-^q(ⁿ), не

q

делится на q^l, следовательно, не делится наи поэтому не сравним с 0 по модулю п. Мы доказали, что если п — составное, то сравне­ ние (22.3) не имеет места. □

Из предложения 22.2 следует, что для проверки простоты числа п можно взять любое а, взаимно простое с п (подходит, например, 1), и проверить (22.3). Но прямая такая проверка потребует П(п) = П(2^т) битовых операций, так как раскрытие скобок в левой части (22.3) дает п + 1 слагаемое. Алгоритм AKS предписывает проверку (22.3) по двум модулям

{х-а)^п=х^п-а (mod х^г - 1, п), (22.4)

г > 0. Сравнение (22.4) понимается в том смысле, что все коэффи­циенты остатка от деления полинома (х - а)" - х^п + а на х^г - 1 (они будут целыми числами) делятся на п. Вычисление остатков от деле­ния (х - а)" и х" на х^г - 1 производится с помощью бинарного ал­горитма возведения в степень, результат каждого умножения сразу же заменяется остатком от деления на х^г - 1. Но если взять произ­вольное г g N⁺, то может оказаться, что (22.4) выполняется и при некоторых составных п. Число г должно подбираться специальным образом, и авторы показывают, что подходящее для целей алгорит­ма г всегда существует и может быть выбрано без существенных за­трат так, что г = 0{т^ъ); после выбора г сравнение (22.4) надо прове­рить для «небольшого» числа «легко определяемых» а — количество этих а есть 0{-^гт). Итоговая сложность алгоритма допускает оцен­ку 0{т^1г). Заметим попутно, что в литературе по теории сложности часто используются оценки вида 0{f{m)) (О называется «О мягкое»),

150