Просмотр кода страницы Сертификат простоты

В [[Математика|математике]] и [[Информатика|информатике]] '''сертификат простоты''' — это строгое доказательство того, что число является [[Простое число|простым]]. Наличие сертификата простоты позволяет проверить, что число простое, не прибегая к [[Тест простоты|тестам простоты]].

В [[Вычислительная сложность|теории сложности вычислений]], как правило, подразумевается, что размер сертификата, как и время, необходимое для его проверки, полиномиально зависит от длины записи числа, то есть, от количества цифр в нём.

Существование полиномиальных сертификатов простоты показывает, что такие задачи как [[Тест простоты|проверка простоты]] и [[Факторизация целых чисел|факторизация]] целых чисел принадлежат [[Класс NP|классу NP]], так как по одному из эквивалентных определений данного класса это такие задачи, решение которых может быть проверено за полиномиальное время если будет дополнительно предоставлен сертификат. Кроме того, эти задачи лежат в классе [[Класс co-NP|co-NP]], что следует из его определения как класса дополнений к задачам из NP — действительно, полиномиальным сертификатом того, что число является составным может быть любой его нетривиальный делитель.

Таким образом, сертификаты простоты были одним из первых свидетельств того, что проверка простоты не является [[NP-полная задача|NP-полной задачей]], так как если бы она была таковой, из этого бы следовало, что класс NP вложен в co-NP, что в свою очередь обычно{{уточнить}} считается{{кем}} неверным. Кроме того, открытие полиномиальных сертификатов сделало проверку простоты первой задачей, про которую было известно, что она принадлежит как NP, так и co-NP, но про которую неизвестно, лежит ли она в классе P. С появлением [[Тест Агравала — Каяла — Саксены|теста Агравала — Каяла — Саксены]] в 2002 г., первого (и единственного на текущий момент{{когда}}) детерминированного полиномиального теста простоты, было установлено, что задача всё же лежит в P.

== Сертификат Пратта ==
Исторически концепция сертификатов простоты была введена с появлением '''сертификата Пратта''', который был получен в 1975 г. [[Пратт, Воган Рональд|Воганом Праттом]]<ref>Vaughan Pratt. «Every prime has a succinct certificate». ''SIAM Journal on Computing'', vol. 4, pp. 214—220. 1975. [http://citeseer.ist.psu.edu/context/39245/0 Citations] {{Wayback|url=http://citeseer.ist.psu.edu/context/39245/0 |date=20080606085156 }}, [http://boole.stanford.edu/pub/SucCert.pdf Full-text] {{Wayback|url=http://boole.stanford.edu/pub/SucCert.pdf |date=20110526205145 }}.</ref>, который описал его структуру и доказал, что размер сертификата полиномиально зависит от длины записи числа, а также что он может быть верифицирован за полиномиальное время. Сертификат основывается на [[Тест простоты Люка|тесте Люка]], который в свою очередь следует из [[Малая теорема Ферма|малой теоремы Ферма]]:

{{Теорема|'''(Теорема Люка)''' Число <math>p</math> является простым тогда и только тогда когда в кольце остатков по модулю <math>p</math> существует элемент <math>a \in \Z_p</math> такой что:
# <math>a^{p-1}\equiv 1 \pmod p</math>,
# <math>a^{\frac{p-1}{q} } \not\equiv 1 \pmod p</math> для всех ''простых'' чисел <math>q</math>, которые делят <math>p-1</math>.}}
{{Доказательство|Записанные условия в точности значат, что [[Порядок элемента группы|порядок]] элемента <math>a</math> равен <math>p-1</math>.
# Если такой элемент существует, то хотя бы <math>p-1</math> элементов кольца остатков по модулю <math>p</math> обратимы, то есть, взаимно просты с <math>p</math>. Таким образом, все числа <math>1,2,\dots,p-1</math> взаимно просты с <math>p</math>, из чего следует простота этого числа.
# Если число <math>p</math> простое, то в кольце остатков по модулю <math>p</math> есть [[Первообразный корень (теория чисел)|первообразный корень]], порядок которого обязан быть равен <math>p-1</math>.}}

Имея такое число <math>a</math> (называемое ''свидетелем простоты'') и разбиение <math>p-1</math> на простые сомножители, можно быстро проверить приведённые условия — нужно выполнить <math>O(\log p)</math> возведений в степень по модулю, что может быть сделано за <math>O(\log p)</math> умножений с помощью [[Алгоритмы быстрого возведения в степень|двоичного возведения в степень]]. Сами же умножения в наивной реализации («в столбик») выполняются за <math>O(\log^2 p)</math>, что даёт общую оценку времени работы в <math>O(\log^4 p)</math>.

При этом стоит иметь в виду, что помимо приведённых условий нужно также проверить, что числа, представленные в сертификате как простые, действительно таковыми являются — таким образом, помимо свидетеля простоты и разбиения <math>p-1</math> на простые сомножители сертификат простоты числа <math>p</math> должен также включать в себя сертификаты простоты всех указанных в нём сомножителей. Таким образом, сертификат удобно представлять в виде дерева, в узлах которого находятся простые числа и соответствующие им свидетели простоты, а потомками узла, в котором хранится число <math>p</math> являются простые делители числа <math>p-1</math>. Соответственно, листьям дерева соответствует число <math>p=2</math>.

Можно показать по индукции, что в таком дереве не больше <math>4\log_2 p - 4</math> внутренних узлов, то есть, таких, которые содержат нечётное простое число. Учитывая, что каждый узел дерева хранит <math>O(\log p)</math> бит для записи чисел в нём, можно заключить, что общий размер дерева не превосходит <math>O(\log^2 p)</math>. Общее время проверки в свою очередь может быть оценено как <math>O(\log^5 p)</math>, так как нужно сделать <math>O(\log^4 p)</math> действий в каждом из <math>O(\log p)</math> узлов.

В то время как сертификаты Пратта полезны в теории и легко проверяются, нахождение сертификата для числа <math>n</math> требует факторизации <math>n-1</math> и прочих потенциально больших чисел. Это просто сделать в некоторых частных случаях, например, для [[Простые числа Ферма|простых чисел Ферма]], но в общем случае эта задача сейчас гораздо сложнее обычной проверки числа на простоту.

== Влияние на «PRIMES is in P» ==
Статья «PRIMES is in P»<ref name="AKS">{{статья |ссылка=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |заглавие=PRIMES is in P |издание=[[Annals of Mathematics]] |том=160 |номер=2 |страницы=781—793 |doi=10.4007/annals.2004.160.781 |jstor=3597229 |mr=2123939 |язык=en |автор=Agrawal, Manindra; {{Нп3|Kayal, Neeraj|Kayal, Neeraj||Neeraj Kayal}}; {{Нп3|Saxena, Nitin|Saxena, Nitin||Nitin Saxena}} |месяц=9 |год=2004 |тип=journal |archivedate=2017-12-07 |archiveurl=https://web.archive.org/web/20171207171714/http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf }}</ref> стала прорывом в [[Теоретическая информатика|теоретической информатике]]. В этой статье, опубликованной Маниндрой Агравалом и его двумя студентами Нираджем Каялом и Нитином Саксеной в августе 2002 г., доказывается, что знаменитая задача проверки числа на простоту может быть детерминированно решена за полиномиальное время. Авторы стали лауреатами [[Премия Гёделя|премии Гёделя]], которая составляет $5000<ref name=Godël2017>{{cite web|title=2017 Gödel Prize|url=https://www.eatcs.org/index.php/component/content/article/1-news/2450-2017-godel-prize|website=European Association for Theoretical Computer Science|publisher=EATCS|accessdate=2017-03-29|archive-date=2019-04-16|archive-url=https://web.archive.org/web/20190416003505/https://www.eatcs.org/index.php/component/content/article/1-news/2450-2017-godel-prize|deadlink=no}}</ref> и [[Премия Фалкерсона|премии Фалкерсона]] 2006 года за свою работу.

В силу того, что проверка простоты теперь может проведена за полиномиальное время с помощью [[Тест Агравала — Каяла — Саксены|теста AKS]], простое число может рассматриваться как сертификат своей собственной простоты. Данный тест выполняется за время <math>\tilde O(\log^6 n)</math>, что делает такую проверку более затратной, чем с помощью сертификата Пратта, однако не требует нахождения самого сертификата.

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

== Ссылки ==
* [http://mathworld.wolfram.com/PrimalityCertificate.html Mathworld: Primality Certificate]
* [http://mathworld.wolfram.com/PrattCertificate.html Mathworld: Pratt Certificate]
* [http://mathworld.wolfram.com/Atkin-Goldwasser-Kilian-MorainCertificate.html Mathworld: Atkin-Goldwasser-Kilian-Morain Certificate]
* [[Vašek Chvátal]]. [https://web.archive.org/web/20060104210644/http://www.cs.rutgers.edu/~chvatal/notes/ppp/ppp.html Lecture notes on Pratt’s Primality Proofs]. Department of Computer Science. Rutgers University. [http://www.cs.concordia.ca/~chvatal/notes/ppp.pdf PDF version at Concordia University].

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


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