Тест на простоту AKS - AKS primality test

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

Важность

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

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

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

Концепции

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

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

(1)

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

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

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

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

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

${ Displaystyle (х + а) ^ {п} эквив (х ^ {п} + а) { pmod {х ^ {г} -1, п}}}$

(2)

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

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

(3)

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

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

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

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

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

В ответ на некоторые из этих вариантов, а также на другие отзывы, статья "PRIMES is in P" была обновлена ​​новой формулировкой алгоритма AKS и доказательства его правильности. (Эта версия была опубликована в Анналы математики.) Хотя основная идея осталась прежней, р был выбран по-новому, и доказательство правильности было организовано более последовательно. Новое доказательство опиралось почти исключительно на поведение циклотомические многочлены над конечные поля. Новая верхняя граница временной сложности была ${ Displaystyle { тильда {O}} ( log (п) ^ {10.5})}$, позже сокращено с использованием дополнительных результатов из теория сита к ${ Displaystyle { тильда {O}} ( log (п) ^ {7.5})}$.

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

Алгоритм

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

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

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

   если (Икс+а)^п≠ Икс^п+а (мод Икс^р − 1,п), выход составной;

6. Вывод премьер.

Здесь ord_р(п) это мультипликативный порядок из п по модулю р, бревно₂ это двоичный логарифм, и ${ displaystyle varphi (r)}$ является Функция Эйлера из р.

Шаг 3 показан в документе как проверка 1 <(а,п) < п для всех а ≤ р. Видно, что это эквивалентно пробному разделению до р, что можно сделать очень эффективно без использования 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} / (п) =: mathbb {Z} _ {п}}$ который имеет ${ displaystyle n}$ элементы, все они кодируются в ${ Displaystyle журнал _ {2} (п)}$ биты.

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

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

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

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

${ Displaystyle и не Equiv v ; { bigl (} { text {mod}} (x ^ {r} ! ! - ! ! 1), п { bigr)}}$

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

${ Displaystyle и эквив v ; { bigl (} { text {mod}} (x ^ {r} ! ! - ! ! 1) { bigr)} quad подразумевает quad u not Equiv v ; ({ text {mod}} n)}$,

так что после сведения к р одночлены с помощью ${ displaystyle { text {mod}} (х ^ {r} ! ! - ! ! 1)}$ Только ${ Displaystyle и не эквив v ; ({ text {mod}} п)}$нужно проверить.^[1]

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

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

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

^[6]

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

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

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

внешняя ссылка

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