Тест на простоту AKS

Алгоритм проверки простых чисел

Тест простоты AKS (также известный как тест простоты Агравала-Кайала-Саксены и циклотомический тест AKS ) — это детерминированный алгоритм доказательства простоты, созданный и опубликованный Маниндрой Агравалом , Нираджем Каялом и Нитином Саксеной , учеными-компьютерщиками из Индийского технологического института Канпура. 6 августа 2002 г., в статье под названием «ПРАЙМЫ находятся в P». ^[1] Алгоритм был первым, который способен за полиномиальное время определить , является ли данное число простым или составным , и это не полагаясь на математические догадки , такие как обобщенная гипотеза Римана . Доказательство также примечательно тем, что не опирается на область анализа . ^[2] В 2006 году авторы получили за свою работу премию Гёделя и премию Фулкерсона .

Важность

AKS — первый алгоритм доказательства простоты, который одновременно является общим , полиномиальным , детерминированным и безусловно правильным . Предыдущие алгоритмы разрабатывались веками и достигали максимум трех из этих свойств, но не всех четырех.

• Алгоритм AKS можно использовать для проверки простоты любого заданного общего числа. Известно множество быстрых тестов на простоту, которые работают только для чисел с определёнными свойствами. Например, критерий Люка-Лемера работает только для чисел Мерсенна , а критерий Пепена можно применять только к числам Ферма .
• Максимальное время работы алгоритма может быть ограничено полиномом от количества цифр в целевом числе. ECPP и APR убедительно доказывают или опровергают то, что данное число является простым, но неизвестно, имеют ли полиномиальные границы времени для всех входных данных.
• Алгоритм гарантированно определит , является ли целевое число простым или составным. Рандомизированные тесты, такие как Миллер-Рабин и Бэйли-PSW , могут проверить любое заданное число на простоту за полиномиальное время, но, как известно, дают только вероятностный результат.
• Корректность AKS не зависит от какой-либо дополнительной недоказанной гипотезы . Напротив, версия теста Миллера-Рабина Миллера полностью детерминирована и работает за полиномиальное время для всех входных данных, но ее правильность зависит от истинности еще не доказанной обобщенной гипотезы Римана .

Хотя алгоритм имеет огромное теоретическое значение, на практике он не используется, что делает его галактическим алгоритмом . Для 64-битных входных данных тест Бэйли-ПСВ является детерминированным и выполняется на много порядков быстрее. Для больших входных данных производительность тестов ECPP и APR (также безусловно правильных) намного превосходит AKS. Кроме того, ECPP может выводить сертификат простоты , который позволяет осуществлять независимую и быструю проверку результатов, что невозможно при использовании алгоритма AKS.

Концепции

Тест на простоту AKS основан на следующей теореме: Учитывая целое и целое число , взаимно простое с , является простым тогда и только тогда, когда полиномиальное отношение сравнения ${\displaystyle n\geq 2}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle n}$

выполняется внутри кольца многочленов . ^[1] Обратите внимание, что обозначает неопределенность , которая порождает это кольцо многочленов. ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]}$ ${\displaystyle X}$

Эта теорема является обобщением на полиномы малой теоремы Ферма . В одном направлении это можно легко доказать, используя биномиальную теорему вместе со следующим свойством биномиального коэффициента :

${\displaystyle {n \choose k}\equiv 0{\pmod {n}}}$для всех , если является простым. ${\displaystyle 0<k<n}$ ${\displaystyle n}$

Хотя соотношение ( 1 ) само по себе представляет собой тест на простоту, его проверка занимает экспоненциальное время : подход грубой силы потребует расширения полинома и уменьшения результирующих коэффициентов. ${\displaystyle (X+a)^{n}}$ ${\displaystyle {\pmod {n}}}$ ${\displaystyle n+1}$

Сравнение представляет собой равенство в кольце полиномов . Вычисление в факторкольце создает верхнюю границу степени задействованных многочленов. AKS оценивает равенство в , делая сложность вычислений зависимой от размера . Для наглядности в ^[1] это выражается сравнением ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]/(X^{r}-1)}$ ${\displaystyle r}$

что то же самое, что:

для некоторых полиномов и . ${\displaystyle f}$ ${\displaystyle g}$

Обратите внимание, что все простые числа удовлетворяют этому соотношению (выбор в ( 3 ) дает ( 1 ), что справедливо для простых чисел). Это сравнение можно проверить за полиномиальное время, если оно полиномиально по отношению к цифрам числа . Алгоритм AKS оценивает это соответствие для большого набора значений, размер которого является полиномиальным по отношению к цифрам . Доказательство справедливости алгоритма AKS показывает, что можно найти набор значений с указанными выше свойствами, такой, что если сравнения выполнены, то это степень простого числа. ^[1] ${\displaystyle g=0}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle a}$ ${\displaystyle n}$

История и время работы

В первой версии цитируемой выше статьи авторы доказали, что асимптотическая временная сложность алгоритма равна (используя Õ из обозначения большого O ) — двенадцатой степени количества цифр в n , умноженной на полилогарифмический множитель. количество цифр. Однако эта верхняя граница была довольно свободной; широко распространенная гипотеза о распределении простых чисел Софи Жермен , если бы она была верной, немедленно сократила бы худший случай до . ${\displaystyle {\tilde {O}}(\log(n)^{12})}$ ${\displaystyle {\tilde {O}}(\log(n)^{6})}$

Через несколько месяцев после открытия появились новые варианты (Lenstra 2002, Pomerance 2002, Berrizbeitia 2002, Cheng 2003, Bernstein 2003a/b, Lenstra и Pomerance 2003), которые значительно увеличили скорость вычислений. Из-за существования множества вариантов Крэндалл и Пападопулос ссылаются на «класс AKS» алгоритмов в своей научной статье «О реализации тестов простоты класса AKS», опубликованной в марте 2003 года.

В ответ на некоторые из этих вариантов, а также на другие отзывы, статья «ПРАЙМЫ в P» была дополнена новой формулировкой алгоритма AKS и доказательством его корректности. (Эта версия в конечном итоге была опубликована в «Анналах математики» .) Хотя основная идея осталась прежней, r было выбрано по-новому, а доказательство правильности было организовано более последовательно. Новое доказательство опиралось почти исключительно на поведение круговых многочленов над конечными полями . Новая верхняя граница временной сложности была позже уменьшена с использованием дополнительных результатов теории решета до . ${\displaystyle {\tilde {O}}(\log(n)^{10.5})}$ ${\displaystyle {\tilde {O}}(\log(n)^{7.5})}$

В 2005 году Померанс и Ленстра продемонстрировали вариант AKS, работающий в эксплуатации, ^[3] что привело к созданию еще одной обновленной версии статьи. ^[4] Агравал, Каял и Саксена предложили вариант, который был бы применим, если бы гипотеза Агравала была верна; однако эвристический аргумент Померанса и Ленстры предполагает, что это, вероятно, неверно. ${\displaystyle {\tilde {O}}(\log(n)^{6})}$ ${\displaystyle {\tilde {O}}(\log(n)^{3})}$

Алгоритм

Алгоритм следующий: ^[1]

Входные данные: целое число n  > 1 .

1. Проверьте, является ли n полной степенью : если n  =  a ^b для целых чисел a  > 1 и b  > 1 , выведите составной результат .
2. Найдите наименьший r такой, что ord _r ( n ) > (log ₂ n ) ² . (если r и n не взаимно просты, пропустите этот r )
3. Для всех 2 ≤ a ≤ min ( r , n −1) проверьте, что a не делит n : Если a | n для некоторых 2 ≤ a ≤ min ( r , n −1), вывести составной результат .
4. Если n ≤ r , выведите prime .
5. Для a =  1 сделать ${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor }$

   если ( X + a ) ⁿ ≠ X ⁿ + a (mod X ^r − 1, n ), вывести составной результат ;

6. Выходное простое число .

Здесь ord _r ( n ) — мультипликативный порядок n по модулю r , log ₂ — двоичный логарифм , а функция Эйлера от r — тотент . ${\displaystyle \varphi (r)}$

Шаг 3 показан в статье как проверка 1 < ( a , n ) < n для всех a ≤ r . Видно, что это эквивалентно пробному делению до r , которое можно сделать очень эффективно без использования gcd . Аналогичным образом, сравнение на шаге 4 можно заменить, если пробное деление возвращает простое число после проверки всех значений до ${\displaystyle \left\lfloor {\sqrt {n}}\right\rfloor .}$

Если выйти за пределы очень небольших затрат, шаг 5 будет доминировать по затраченному времени. Существенное снижение сложности (от экспоненциальной до полиномиальной) достигается за счет выполнения всех вычислений в конечном кольце.

${\displaystyle R:=(\mathbb {Z} /n\mathbb {Z} )[X]/(X^{r}-1)}$

состоящее из элементов. Это кольцо содержит только мономы и коэффициенты , в которых есть элементы, все из которых можно закодировать в битах. ${\displaystyle n^{r}}$ ${\displaystyle r}$ ${\displaystyle \{X^{0},X^{1},\ldots ,X^{r-1}\}}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle n}$ ${\displaystyle \log _{2}(n)}$

Большинство более поздних улучшений, внесенных в алгоритм, были сосредоточены на уменьшении размера r , что ускоряет основную операцию на шаге 5, а также на уменьшении размера s , количества циклов, выполняемых на шаге 5. ^[5] Обычно эти изменения не изменить вычислительную сложность, но может привести к сокращению времени на многие порядки, например, окончательная версия Бернштейна имеет теоретическое ускорение более чем в 2 миллиона раз.

Схема подтверждения действительности

Чтобы алгоритм был корректным, все шаги, определяющие n, должны быть корректными. Шаги 1, 3 и 4 тривиально корректны, поскольку основаны на прямых проверках делимости n . Шаг 5 также верен: поскольку (2) верно для любого выбора чисел , взаимно простых с n и r , если n простое, неравенство означает, что n должно быть составным.

Самая трудная часть доказательства — показать, что шаг 6 верен. Его доказательство правильности основано на верхних и нижних границах мультипликативной группы , построенной из биномов ( X + a ), которые проверяются на шаге 5. Шаг 4 гарантирует, что эти биномы являются различными элементами . Для конкретного выбора r границы приводят к противоречию , если только n не является простым или степенью простого числа. Вместе с тестом шага 1 это означает, что n всегда простое на шаге 6. ^[1] ${\displaystyle \mathbb {Z} _{n}[x]}$ ${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor }$ ${\displaystyle \mathbb {Z} _{n}[x]}$

Пример 1: n = 31 — простое число

 Входные данные : целое число n = 31 > 1. (* Шаг 1 *)  Если ( n = a b для целых чисел a > 1 и b > 1), выведите  составной результат . For ( b = 2; b <= log 2 (n); b++) { а = п 1/б ; Если (a — целое число), верните [составное] } а = n 1/2 ...n 1/4 = {5,568, 3,141, 2,360} (* Шаг 2 *) Найдите наименьший r такой, что Or r ( n ) > (log 2  n ) 2 . maxk = ⌊(log 2 n) 2 ⌋; maxr = Max[3, ⌈(Log 2 n) 5 ⌉]; (* maxr действительно не нужен *) следующийR = Истина; For (r = 2; nextR && r < maxr; r++) { следующийR = Ложь; For (k = 1; (!nextR) && k ≤ maxk; k++) { nextR = (Mod[n k , r] == 1 || Mod[n k , r]==0) } } р--; (*цикл увеличивается на единицу*)  р = 29 (* Шаг 3 *)  Если (1 < НОД ( a , n ) < n для некоторого a ≤ r ), выведите  составной результат . For (a = r; a > 1; a--) { If ((gcd = НОД[a,n]) > 1 && НОД < n), Return [Composite] }  НОД = {НОД(29,31)=1, НОД(28,31)=1, ..., НОД(2,31)=1} ≯ 1 (* Шаг 4 *)  Если ( n ≤ r ), выведите  prime . Если (n ≤ r), верните [Prime] (* этот шаг можно пропустить, если n > 5690034 *)  31 > 29  (* Шаг 5 *)  Для a  = 1 сделать  If (( X + a ) n ≠ X n + a (mod X r − 1, n )), вывести составной ; ${\displaystyle \left\lfloor {\sqrt {\varphi (r)}}\log _{2}(n)\right\rfloor }$     φ[x_] := EulerPhi[x]; PolyModulo[f_] := PolynomialMod[ PolynomialRemainder [f, x r -1, x], n]; макс = Этаж[Log[2, n] √ φ[r] ]; For (a = 1; a ≤ max; a++) { If (PolyModulo[(x+a) n - PolynomialRemainder[x n +a, x r -1], x] ≠ 0) { Return [Composite] { }  (х+а) 31 = a 31 +31a 30 x +465a 29 x 2 + 4495a 28 x 3 +31465a 27 x 4 +169911a 26 x 5 +736281a 25 x 6 +2629575a 24 x 7 + 7888725a 23 x 8 + 20160075a 22 x 9 [phone]а 21 х 10 [phone]a 20 x 11 [phone]a 19 x 12 [phone]a 18 x 13 [phone]a 17 x 14 + 300540195a 16 x 15 + 300540195a 15 x 16 + 265182525a 14 х 17 + 206253075a 13 х 18 [phone]a 12 х 19 [phone]a 11 х 20 [phone]a 10 x 21 [phone]a 9 x 22 +7888725a 8 x 23 +2629575a 7 x 24 +736281a 6 x 25 +169911a 5 x 26 + 31465a 4 x 27 + 4495a 3 x 28 + 465a 2 х 29 +31 токс 30 + х 31  PolynomialRemainder [(x+a) 31 , x 29 -1] = 465a 2 +a 31 +(31a+31a 30 )x +(1+465a 29 )x 2 +4495a 28 x 3 +31465a 27 x 4 + 169911a 26 x 5 +736281a 25 x 6 +2629575a 24 x 7 +7888725a 23 x 8 [phone]a 22 x 9 + 44352165a 21 x 10 [phone]a 20 x 11 [phone]a 19 x 12 + 206253075a 18 x 13 [phone]a 17 x 14 + 300540195a 16 x 1 5 + 300540195a 15 x 16 [phone]a 14 x 17 [phone]a 13 x 18 + 141120525a 12 x 19 [phone]a 11 x 20 [phone]a 10 x 21 [phone]a 9 x 22 + 7888725a 8 x 23 +2629575a 7 x 24 + 736281a 6 x 25 + 169911a 5 х 26 + 31465а 4 х 27 +4495а 3 х 28  ( A ) PolynomialMod [PolynomialRemainder [(x+a) 31 , x 29 -1], 31] = a 31 +x 2  ( B ) PolynomialRemainder [x 31 +a, x 29 -1] = a+x 2  ( А ) - ( B ) знак равно а 31 +х 2 - (а+х 2 ) знак равно а 31 -а   ${\displaystyle \max =\left\lfloor \log _{2}(31){\sqrt {\varphi (29)}}\right\rfloor =26}$  {1 31 -1 = 0 (по модулю 31), 2 31 -2 = 0 (по модулю 31), 3 31 -3 = 0 (по модулю 31), ..., 26 31 -26 = 0 (по модулю 31)}  (* Шаг 6 *)  Выведите  prime . 31 Должно быть премьер

Где PolynomialMod — это уменьшение полинома по модулю. например PolynomialMod[x+2x ² +3x ³ , 3] = x+2x ² +0x ³

^[6]

Рекомендации

1. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004). «ПРАЙМС находится в P» (PDF) . Анналы математики . 160 (2): 781–793. дои : 10.4007/анналы.2004.160.781 . JSTOR  3597229.
2. Гранвилл, Эндрю (2005). «Легко определить, является ли данное целое число простым». Бык. амер. Математика. Соц . 42 : 3–38. дои : 10.1090/S0273-0979-04-01037-7 .
3. HW Ленстра-младший и Карл Померанс, «Тестирование простоты с гауссовскими периодами», предварительная версия 20 июля 2005 г.
4. HW Ленстра-младший и Карл Померанс, «Тестирование простоты с гауссовскими периодами. Архивировано 25 февраля 2012 г. в Wayback Machine », версия от 12 апреля 2011 г.
5. Дэниел Дж. Бернштейн, «Доказательство первичности после Агравала-Каяла-Саксены», версия от 25 января 2003 г.
6. См. страницу обсуждения AKS , где обсуждается, почему отсутствует «Пример 2: n не является простым после шага 4».

дальнейшее чтение

• Дитцфельбингер, Мартин (2004). Проверка простоты за полиномиальное время. От рандомизированных алгоритмов к PRIMES в P. Конспекты лекций по информатике. Том. 3000. Берлин: Springer-Verlag . ISBN 3-540-40344-2. Збл  1058.11070.

Внешние ссылки

• Вайсштейн, Эрик В. «Тест на примитивность AKS». Математический мир .
• Р. Крэндалл, Apple ACG и Дж. Пападопулос (18 марта 2003 г.): О реализации тестов простоты класса AKS (PDF)
• Статья Борнемана, содержащая фотографии и информацию о трех индийских ученых (PDF)
• Эндрю Грэнвилл: Легко определить, является ли данное целое число простым
• Основные факты: от Евклида до АКС, Скотт Ааронсон (PDF)
• PRIMES находится в P small FAQ от Антона Стиглича
• Цитирование премии Гёделя 2006 г.
• Цитирование премии Фулкерсона 2006 г.
• Ресурс по алгоритму AKS "PRIMES in P"