Просмотр кода страницы Тест Агравала — Каяла — Саксены

'''Тест Аграва́ла — Кая́ла — Саксе́ны''' ('''тест AKS''') — единственный известный на данный момент универсальный (то есть применимый ко всем числам) [[Полиномиальный алгоритм|полиномиальный]], [[Детерминированный алгоритм|детерминированный]] и безусловный (то есть не зависящий от недоказанных гипотез) [[тест простоты]] чисел, основанный на обобщении [[Малая теорема Ферма|малой теоремы Ферма]] на многочлены.

== Формулировка ==
{{Теорема|1=Если существует <math>r\in\mathbb{Z}</math> такое, что <math>o_r(n)>\log^2 n</math> и для любого <math>a</math> от 1 до <math>\left\lfloor\sqrt{\varphi(r)}\log(n)\right\rfloor</math> выполняется [[сравнение по модулю|сравнение]] <math>(x+a)^n\equiv(x^n+a)\pmod{x^r-1,\;n}</math>,<br>то <math>n</math> — либо простое число, либо степень простого числа.
}}

Здесь и далее <math>o_r(n)</math> обозначает [[Показатель числа по модулю|показатель числа <math>n</math> по модулю <math>r</math>]], <math>\log</math> — [[двоичный логарифм]] и <math>\varphi(\cdot)</math> — [[функция Эйлера]]{{sfn|Агафонова|2009}}.

Сравнение по двум модулям вида
: <math>a(x)\equiv b(x)\pmod{h(x),\;n}</math>
для многочленов <math>a(x),\;b(x)\in\Z[x]</math> означает, что существует <math>g(x)\in\Z[x]</math> такой, что все коэффициенты многочлена <math>a(x)-b(x)-g(x)h(x)</math> кратны <math>n</math>, где <math>\Z[x]</math> — [[кольцо многочленов]] от <math>x</math> над целыми числами{{sfn|Агафонова|2009}}.

== История ==
Тест AKS был предложен [[Индия|индийским]] учёным {{не переведено|Маниндра Агравал|Мани́ндрой Аграва́лом|en|Manindra_Agrawal}} и его двумя студентами {{не переведено|Нирадж Каял|Ни́раджем Кая́лом|en|Neeraj_Kayal}} и {{не переведено|Нитин Саксена|Нити́ном Саксе́ной|en|Nitin_Saxena}} {{не переведено|Индийский технический институт Канпура|Индийского технического института Канпура|en|Indian_Institute_of_Technology_Kanpur}} и впервые опубликован [[6 августа]] [[2002 год в науке|2002 года]]{{sfn|Agrawal, Kayal, Saxena|2004}}. До этой публикации принадлежность задачи распознавания простоты [[класс P|классу P]] являлась [[Открытые математические проблемы|открытой проблемой]].

Вычислительная сложность изначального алгоритма оценивается как <math>\mathcal{O}(\log^{21/2}n)</math>. В предположении верности [[Гипотеза Артина|гипотезы Артина]], время выполнения улучшается до <math>\mathcal{O}(\log^6 n) </math>. В предположении верности [[Числа Софи Жермен|гипотезы Софи Жермен]] время также стремится к <math>\mathcal{O}(\log^6 n)</math>{{sfn|Agrawal, Kayal, Saxena|2004}}.

В [[2005 год в науке|2005 году]] [[Ленстра, Хендрик|Ленстра]] и [[Померанс, Карл|Померанс]] опубликовали улучшенный вариант алгоритма с [[Вычислительная сложность|вычислительной сложностью]] <math>\mathcal{O}(\log^6 n)</math>, где <math>n</math> — проверяемое тестом число<ref name="lenstra_pomerance_2005">H. W. Lenstra Jr. and Carl Pomerance, «[http://www.math.dartmouth.edu/~carlp/PDF/complexity12.pdf Primality Testing with Gaussian Periods] {{Wayback|url=http://www.math.dartmouth.edu/~carlp/PDF/complexity12.pdf |date=20210428084131 }}», preliminary version July 20, 2005.</ref><ref name="lenstra_pomerance_2011">H. W. Lenstra Jr. and Carl Pomerance, «[http://www.math.dartmouth.edu/~carlp/aks041411.pdf Primality testing with Gaussian periods] {{Wayback|url=http://www.math.dartmouth.edu/~carlp/aks041411.pdf |date=20120225052810 }}», version of April 12, 2011.</ref>.

Согласно [[Гипотеза Агравала|гипотезе Агравала]] существует вариант алгоритма с временем выполнения <math>\mathcal{O}(\log^3 n) </math>, но Ленстра и Померанс привели [[Эвристика|эвристический аргумент]], подтверждающий ложность этой гипотезы{{sfn|Agrawal, Kayal, Saxena|2004}}.

Данный алгоритм имеет важное теоретическое значение, но на практике не применяется, так как его [[вычислительная сложность]] значительно выше, чем у лучших вероятностных алгоритмов{{sfn|Бараш|2005}}. За своё открытие авторы получили [[Премия Гёделя|премию Гёделя]] и [[Премия Фалкерсона|премию Фалкерсона]] в [[2006 год в науке|2006 году]]{{sfn|Cao, Liu|2014}}.

== Основные свойства ==
Основное свойство алгоритма заключается в том, что он одновременно ''универсален'', ''полиномиален'', ''детерминирован'' и ''безусловен''{{sfn|Бараш|2005}}, предыдущие алгоритмы обладали максимум лишь тремя из этих четырёх свойств.

Универсальность теста означает, что он может использоваться для проверки простоты любых чисел. Многие быстрые тесты предназначены для проверки чисел из ограниченного множества. Например, [[тест Люка — Лемера]] работает только для [[Числа Мерсенна|чисел Мерсенна]], а [[тест Пепина]] применим лишь к [[Числа Ферма|числам Ферма]]{{sfn|Cao, Liu|2014}}.

[[Полиномиальный алгоритм|Полиномиальность]] означает, что наибольшее время работы алгоритма ограничено [[многочлен]]ом от количества цифр в проверяемом числе. При этом такие тесты, как [[тест эллиптических кривых]] (ECPP) и [[тест Адлемана — Померанса — Румели]] (APR), могут доказать или опровергнуть простоту числа, но для них не доказано, что время работы будет полиномиальным для любого входного числа{{sfn|Cao, Liu|2014}}.

[[Детерминированный алгоритм|Детерминизм]] гарантирует получение уникального предопределённого результата. [[Вероятностная машина Тьюринга|Вероятностные тесты]], такие, как [[тест Миллера — Рабина]] и [[тест Бейли — Померанца — Селфриджа — Уогстаффа]], могут проверить простоту числа за полиномиальное время, но при этом дают лишь вероятностный ответ{{sfn|Cao, Liu|2014}}.

Безусловность — свойство, заключающееся в том, что корректность алгоритма не зависит от каких-либо недоказанных гипотез. Этим свойством не обладает, например, [[Тест Миллера (теория чисел)|Тест Миллера]], который хоть и детерминирован и работает за полиномиальное время для любого входного числа, но его корректность зависит от недоказанной [[гипотеза Римана#Обобщённая гипотезы Римана|обобщённой гипотезы Римана]]{{sfn|Cao, Liu|2014}}.

== Основная идея ==
Основной идеей алгоритма является обобщение [[Малая теорема Ферма|малой теоремы Ферма]] на многочлены, утверждающее, что для всех <math>a\in\Z_n^*</math> (где [[Сравнение по модулю#Классы вычетов|кольцо <math>\Z_n</math>]] взято без обратных элементов по умножению и нулевого элемента) и <math>n \in \N</math>, <math>n</math> — простое тогда и только тогда, когда{{sfn|Agrawal, Kayal, Saxena|2004}}{{sfn|Menon|2007|pp=10—11}}<!-- уточнить год или работу -->{{sfn|Salembier, Southerington|2005}}:

{{Нумерованная формула|:|<math>(x+a)^n\equiv(x^n+a)\pmod{n}.</math>|1|RawN=.}}

Иными словами, если <math>a\in\Z</math>, <math>n\in\N</math>, <math>n\geqslant 2</math> и [[Наибольший общий делитель|НОД]]<math>(a,\;n)=1</math>, то <math>n</math> простое тогда и только тогда, когда выполнено условие '''(1)'''.

На проверку этого выражения требуется время, оцениваемое в <math>\Omega(n)</math>, поскольку в худшем случае следует оценить <math>n</math> коэффициентов в левой части. Для сокращения числа коэффициентов и сложности вычислений было выбрано такое <math>r</math>, чтобы использовать в качестве теста на простоту выражение{{sfn|Agrawal, Kayal, Saxena|2004}}:
: <math> (x+a)^n\equiv (x^n+a)\pmod{x^r-1,\;n},</math>
которое получается делением обеих частей исходного выражения на <math>x^r-1</math>{{sfn|Menon|2007|pp=10—11}}.

Здесь количество подлежащих проверке значений <math>a</math> и значение <math>r</math> уже ограничены многочленом от <math>\log n</math>{{sfn|Salembier, Southerington|2005}}.

В этом случае вместо [[Факторкольцо|факторкольца]] <math>\mathbb{F}_p[x]/\langle x^r-1\rangle</math> рассматривается поле <math>F=\mathbb{F}_p[x]/\langle h\rangle</math>, где <math>h=h(x)</math> — [[неприводимый многочлен|неприводимый делитель]] <math>{x^r-1}</math> над [[Конечное поле|конечным полем]] <math>\mathbb{F}_p</math>, отличный от <math>x-1</math>. Оценивается число многочленов этого поля, для которых выполняется сравнение:
: <math>(x+a)^n\equiv(x^n+a)\pmod{x^r-1,\;n}.</math>

== Алгоритм и его модификация ==
: Ввод: целое число <math>n>1</math>.
# Если <math>n=a^b</math> для целых чисел <math>a>1</math> и <math>b>1</math>, вернуть ''«составное»''.
# Найдем наименьшее <math>r</math>, такое что <math>o_r(n)>(\log_2(n))^2</math>.
# Если <math>1<</math>НОД<math>(a,\;n)<n</math> для некоторого <math>a\leqslant r</math>, вернуть ''«составное»''.
# Если <math>n\leqslant r</math>, вернуть ''«простое»''.
# Если для всех <math>a</math> от 1 до <math>\left\lfloor\sqrt{\varphi(r)}\log(n)\right\rfloor</math> верно, что <math>(x+a)^n\equiv x^n+a\pmod{x^r-1,\;n}</math>, вернуть ''«простое»''.
# Иначе вернуть ''«составное»''.

Агравалом, Каялом и Саксеной доказано, что алгоритм вернёт ''«простое»'' тогда и только тогда, когда <math>n</math> — простое число.

[[Ленстра, Хендрик|Ленстра]] и [[Померанс, Карл|Померанс]] опубликовали улучшенный вариант алгоритма{{sfn|Salembier, Southerington|2005}}<ref name="lenstra_pomerance_2011" />:
: Ввод: <math>n\in\N</math>, <math>n>1</math>
# Если <math>n=a^b</math> для <math>a\in\N</math> и целого <math>b>1</math>, вернуть ''«составное»''.
# Найдем наименьшее <math>r</math> такое что <math>o_r(n)>(log_2(n))^2</math>.
# Если НОД<math>(a,\;n)\neq 1</math> для любого <math>a\leqslant r</math>, вернуть ''«составное»''.
# Если для всех <math>a</math> от 1 до <math>\left\lfloor\sqrt{r}\log n\right\rfloor</math> верно, что <math>(x+a)^n\equiv x^n+a\pmod{\varphi(x),\;n}</math>, вернуть ''«простое»''.
# Иначе вернуть ''«составное»''.

Здесь функция <math>\varphi(x)</math> — та же, <math>x^r-1</math> — многочлен степени, большей <math>\log^2 n</math>, такой, что <math>\varphi(x^n)\equiv 0\pmod{\varphi(x)}</math> при некоторых дополнительных условиях{{sfn|Агафонова|2009}}{{sfn|Salembier, Southerington|2005}}.

Вычислительная сложность этого алгоритма — <math>\mathcal{O}(\log^6 n)</math>.

== Обоснование ==
В обосновании используется [[группа (математика)|группа]] <math>G</math> — группа всех чисел, которые являются вычетами по модулю <math>r</math> для чисел из набора{{sfn|Agrawal, Kayal, Saxena|2004|p=5}}:
: <math>I=\left\{\left(\frac{n}{p}\right)^i\cdot p^j\colon i,\;j\geqslant 0\right\}.</math>
Данная подгруппа, назовём её группой <math>G</math>, уже содержит <math>(n,\;r)=(p,\;r)=1</math>. Группа <math>G</math> порождена <math>n, p</math> по модулю <math>r</math>, и так как <math>o_r(n)>\log^2 n</math>, то <math>|G|=t>\log^2 n</math>.

Вторая группа, используемая в доказательстве, <math>|\mathcal G|</math>, является множеством всех вычетов многочленов в <math>P</math> (пространстве простых чисел) по модулю <math>h(x)</math> и <math>p</math>. Эта группа порождена элементами <math>x,\;x+1,\;x+2,\;\ldots,\;x+l</math> в поле <math>F=\mathbb{F}_p[x]/\langle h(x)\rangle</math> и является подгруппой мультипликативной группы [[конечное поле|поля]] <math>\mathbb{F}_p</math>{{sfn|Agrawal, Kayal, Saxena|2004|p=5}}.

Основные промежуточные леммы и определения, используемые в обосновании алгоритма{{sfn|Agrawal, Kayal, Saxena|2004}}:
* Пусть <math>a,\;n\in\Z</math>, <math>n\geqslant 2</math>, и НОД<math>(a,\;n)=1</math>. Тогда <math>n</math> является [[простое число|простым]] тогда и только тогда, когда
*: <math>(x+a)^n\equiv x^n+a\pmod{n}.</math>
* Пусть НОК<math>(m)</math> обозначает [[наименьшее общее кратное]] первых <math>m</math> чисел. Тогда для <math>m\geqslant 7</math> справедливо неравенство:
*: НОК<math>(m)\geqslant 2^m.</math>
* Существует <math>r</math> такое, что <math>r\leqslant \max\big(3,\;\lceil\log^5 n\rceil\big)</math>, такое что <math>o_r(n)>\log^2n</math>.
* ''Определение.'' Для многочлена <math>f(x)</math> и числа <math>m\in\N </math>, говорится что <math>m</math> ''включено'' в <math>f(x)</math>, если <math>\lceil f(x)\rceil^m\equiv f(x^m)\pmod{x^r-1,\;p}</math>.
* Если числа <math>m</math> и <math>m'</math> включены в <math>f(x)</math>, то их произведение <math>m\cdot m'</math> также включено.
* Если число <math>m</math> включено в <math>f(x)</math> и <math>g(x)</math>, то <math>m</math> так же включено в <math>f(x)\cdot g(x)</math>.
* '''{{anchor2|Лемма Ленстры}}'''. <math>|\mathcal{G}|\geqslant\tbinom{t+l}{t-1}</math>.
* Если <math>n</math> не является степенью <math>p</math>, то <math>|\mathcal G|\leqslant n^\sqrt{t}</math>.

== Практическое применение ==
При оценке параметра <math>r=\mathcal{O}(\log^5 n)</math> алгоритм требует 1 000 000 000 Гб ([[гигабайт]]) памяти для чисел из 1024 бит. Для современных [[Операционная система|операционных систем]] это слишком большой объём информации. В предположении верности [[Гипотеза Артина|гипотезы Артина]] и [[Числа Софи Жермен|гипотезы Софи Жермен]] о [[Плотность множества|плотности множества]] простых чисел для алгоритма будет достаточно значения параметра <math>r</math>, оцениваемого в <math>\mathcal{O}(\log^2 n)</math>. В этом случае будет достаточно 1 [[гигабайт|Гб]] памяти. Но пока верность этих гипотез не доказана, алгоритм не применяется ввиду сложного исполнения. [[Кнут, Дональд Эрвин|Дональд Кнут]], поместивший алгоритм во второй том [[Искусство программирования|Искусства программирования]] (издание 3), в частной переписке отметил его чисто теоретический характер{{sfn|Cao, Liu|2014}}.

== Примечания ==
{{примечания|2}}

== Литература ==
* {{статья|автор=Бараш Л. Ю.|заглавие=Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел|издание=Безопасность информационных технологий|номер=2|год=2005|страницы=27—38|ссылка=http://www.comphys.ru/files/bit-2.pdf|ref=Бараш|archiveurl=https://web.archive.org/web/20141018205118/http://www.comphys.ru/files/bit-2.pdf|archivedate=2014-10-18|url=http://www.comphys.ru/files/bit-2.pdf|deadlink=да}}
* {{статья |автор=Агафонова И. В. |заглавие=Проверка чисел на простоту: полиномиальный алгоритм |издание=Семинар по дискретному гармоническому анализу и геометрическому моделированию |ссылка=http://dha.spb.ru/PDF/AKS.pdf|ref=Агафонова|год=2009}}

'''на английском языке'''
* {{source|Q27018082|ref=Agrawal, Kayal, Saxena|ref-year=2004}} <!-- PRIMES is in P // Annals of Mathematics -->
* R. Crandall, [[Apple]] ACG, J. Papadopoulos, [https://web.archive.org/web/20040710131419/http://images.apple.com/acg/pdf/aks3.pdf On the implementation of AKS-class primality tests], 2003.
* {{source|Q27940956|ref=Salembier, Southerington|ref-year=2005}} <!-- An Implementation of the AKS Primality Test --> — сравнение реализаций изначального алгоритма и алгоритма Ленстры с использованием различных библиотек.
* {{статья|автор=Zhengjun Cao, Lihua Liu|заглавие=Remarks on AKS Primality Testing Algorithm and A Flaw in the Definition of P|ссылка=http://arxiv.org/abs/1402.0146|год=2014|arXiv=1402.0146v1|ref=Cao, Liu}}
* {{source|Q27940963|ref=Granville|ref-year=2005}} <!-- It is easy to determine whether a given integer is prime // Bull. Amer. Math. Soc. -->
* {{cite web
 |url         = http://www.google.com/patents/US20050027764
 |title       = Polynomial time deterministic method for testing primality of numbers
 |author      = Agrawal, M. and Kayal, N. and Saxena, N.
 |date        = 
 |work        = Patent US 20050027764 A1
 |publisher   =
 |accessdate  = 2013-12-15
 |lang        = en
 |ref         = Agrawal, M. and Kayal, N. and Saxena, N.
}}
* {{книга|автор=Rotella C.|заглавие=An efficient implementation of the aks polynomial-time primality proving algorithm|ссылка=https://www.cs.cmu.edu/afs/cs/user/mjs/ftp/thesis-program/2005/rotella.pdf|место=Pittsburgh, Pennsylvania, USA|издательство=School of Computer Science-Carnegie Mellon University|год=2005|язык=en}}<!-- диссертация, но имеет цитирования -->
* {{статья
 |автор         = Vijay Menon
 |заглавие      = Deterministic Primality Testing — understanding the AKS algorithm
 |ссылка        = http://arxiv.org/abs/1311.3785
 |язык          = en
 |издание       = CoRR
 |год           = 2007
 |том           = abs/1311.3785
 |ref         = Menon
}}

== Ссылки ==
* {{MathWorld| title=AKS Primality Test| urlname=AKSPrimalityTest}} — краткая информация о тесте AKS
* {{cite web|url=http://fatphil.org/maths/AKS|title=The AKS «PRIMES in P» Algorithm Resource|author=Phil Carmody |accessdate=2014-10-19|lang=en}} — обзор материалов, посвящённых алгоритму
* {{статья
 |автор         = Li, H.
 |заглавие      = The Analysis and Implementation of the AKS Algorithm and Its Improvement Algorithms
 |ссылка        = http://opus.bath.ac.uk/16757/1/CSBU-2007-09.pdf
 |язык          = en
 |издание       = 
 |год           = 2013
 |том           = 
 |ref         = Li H.
}}
* {{статья
 |автор         = Pedro Berrizbetia
 |заглавие      = Sharpening «Primes is in P» for a large family of numbers.
 |ссылка        = http://lanl.arxiv.org/pdf/math/0211334v1.pdf
 |язык          = en
 |издание       = 
 |год           = 2011
 |том           = 
 |ref         = Pedro Berrizbetia
}}

{{Теоретико-числовые алгоритмы}}

{{Добротная статья|Теория информации и криптография}}

[[Категория:Тесты простоты]]