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

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

Важность [ править ]

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

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

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

Концепции [ править ]

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

${\ Displaystyle (х + а) ^ {п} \ эквив (х ^ {п} + а) {\ pmod {п}}}$

( 1 )

держит. ^[1] Обратите внимание, что это следует понимать как формальный символ.${\ displaystyle x}$

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

${\ Displaystyle {п \ выбрать k} \ эквив 0 {\ pmod {п}}}$для всех, если прост.${\displaystyle 0<k<n}$${\displaystyle n}$

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

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

${\displaystyle (x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,n}}}$

( 2 )

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

${\displaystyle (x+a)^{n}-(x^{n}+a)=(x^{r}-1)g+nf}$

( 3 )

для некоторых многочленов и .${\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 and Pomerance 2003), которые значительно повысили скорость вычислений. Из-за существования множества вариантов Крэндалл и Пападопулос в своей научной статье «О реализации тестов простоты класса AKS», опубликованной в марте 2003 года, ссылаются на «класс алгоритмов AKS».

В ответ на некоторые из этих вариантов, а также на другие отзывы, статья «PRIMES is in P» была обновлена ​​новой формулировкой алгоритма AKS и доказательства его правильности. (Эта версия в конечном итоге была опубликована в Annals of Mathematics .) Хотя основная идея осталась прежней, r был выбран новым способом, и доказательство правильности было организовано более последовательно. Новое доказательство основывалось почти исключительно на поведении круговых многочленов над конечными полями . Новая верхняя граница временной сложности была позже уменьшена с использованием дополнительных результатов теории решет до .${\displaystyle {\tilde {O}}(\log(n)^{10.5})}$${\displaystyle {\tilde {O}}(\log(n)^{7.5})}$

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

Алгоритм [ править ]

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

Ввод: целое число n  > 1 .

1. Проверьте , если п является идеальной мощность : если п  =  ^б для целых чисел через  > 1 и Ь  > 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 , вывести простое число .
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 _г ( п ) является мультипликативным порядком из п по модулю г , бревенчатый ₂ представляет собой двоичный логарифм , и это totient функция Эйлера из г .${\displaystyle \varphi (r)}$

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

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

${\displaystyle R:={\Bigl (}{\bigl (}\mathbb {Z} /(n){\bigr )}[X]{\Bigr )}{\Bigl /}(X^{r}\!\!-\!\!1){\Bigr .}}$

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

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

Схема доказательства действительности [ править ]

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

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

${\displaystyle u\not \equiv v\;{\bigl (}{\text{mod }}(x^{r}\!\!-\!\!1),n{\bigr )}}$

это эквивалентно

${\displaystyle u\equiv v\;{\bigl (}{\text{mod }}(x^{r}\!\!-\!\!1){\bigr )}\quad \implies \quad u\not \equiv v\;({\text{mod }}n)}$,

так что после сокращения до r мономов с помощью только нужно проверять. ^[1]${\displaystyle {\text{mod }}(x^{r}\!\!-\!\!1)}$${\displaystyle u\not \equiv v\;({\text{mod }}n)}$

Пример 1: n = 31 - простое число [ править ]

Ввод: целое число n  = 31> 1.

Где PolynomialMod - это почленное сокращение полинома по модулю. например, PolynomialMod [x + 2x ² + 3x ³ , 3] = x + 2x ² + 0x ³

^[6]

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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