Влияние на «primes is in p»
Статья «PRIMES is in P»[2] стала прорывом в теоретической информатике. В этой статье, опубликованной Маниндрой Агравалом и его двумя студентами Нираджем Каялом и Нитином Саксеной в августе 2002 г., доказывается, что знаменитая задача проверки числа на простоту может быть детерминированно решена за полиномиальное время.
В силу того, что проверка простоты теперь может проведена за полиномиальное время с помощью теста AKS, простое число может рассматриваться как сертификат своей собственной простоты. Данный тест выполняется за время O~(log6n){displaystyle {tilde {O))(log ^{6}n)}, что делает такую проверку более затратной, чем с помощью сертификата Пратта, однако не требует нахождения самого сертификата.
Примечания
- ↑Vaughan Pratt. «Every prime has a succinct certificate». SIAM Journal on Computing, vol. 4, pp. 214—220. 1975. Citations, Full-text.
- ↑Agrawal, Manindra; Kayal, Neeraj ; Saxena, Nitin .PRIMES is in P (англ.) // Annals of Mathematics : journal. — 2004. — September (vol. 160, no. 2). — P. 781—793. — doi:10.4007/annals.2004.160.781. — .
- ↑2021 Gödel Prize (неопр.). European Association for Theoretical Computer Science. EATCS. Дата обращения: 29 марта 2021.
Сертификат пратта
Исторически концепция сертификатов простоты была введена с появлением сертификата Пратта, который был получен в 1975 г. Воганом Праттом[1], который описал его структуру и доказал, что размер сертификата полиномиально зависит от длины записи числа, а также что он может быть верифицирован за полиномиальное время. Сертификат основывается на тесте Люка, который в свою очередь следует из малой теоремы Ферма:
Доказательство
Записанные условия в точности значат, что порядок элемента a{displaystyle a} равен p−1{displaystyle p-1}.
- Если такой элемент существует, то хотя бы p−1{displaystyle p-1} элементов кольца остатков по модулю p{displaystyle p} обратимы, то есть, взаимно просты с p{displaystyle p}. Таким образом, все числа 1,2,…,p−1{displaystyle 1,2,dots ,p-1} взаимно просты с p{displaystyle p}, из чего следует простота этого числа.
- Если число p{displaystyle p} простое, то в кольце остатков по модулю p{displaystyle p} есть первообразный корень, порядок которого обязан быть равен p−1{displaystyle p-1}.■
Имея такое число a{displaystyle a} (называемое свидетелем простоты) и разбиение p−1{displaystyle p-1} на простые сомножители, можно быстро проверить приведённые условия — нужно выполнить O(logp){displaystyle O(log p)} возведений в степень по модулю, что может быть сделано за O(logp){displaystyle O(log p)} умножений с помощью двоичного возведения в степень. Сами же умножения в наивной реализации («в столбик») выполняются за O(log2p){displaystyle O(log ^{2}p)}, что даёт общую оценку времени работы в O(log4p){displaystyle O(log ^{4}p)}.
При этом стоит иметь в виду, что помимо приведённых условий нужно также проверить, что числа, представленные в сертификате как простые, действительно таковыми являются — таким образом, помимо свидетеля простоты и разбиения p−1{displaystyle p-1} на простые сомножители сертификат простоты числа p{displaystyle p} должен также включать в себя сертификаты простоты всех указанных в нём сомножителей. Таким образом, сертификат удобно представлять в виде дерева, в узлах которого находятся простые числа и соответствующие им свидетели простоты, а потомками узла, в котором хранится число p{displaystyle p} являются простые делители числа p−1{displaystyle p-1}. Соответственно, листьям дерева соответствует число p=2{displaystyle p=2}.
Можно показать по индукции, что в таком дереве не больше 4log2p−4{displaystyle 4log _{2}p-4} внутренних узлов, то есть, таких, которые содержат нечётное простое число. Учитывая, что каждый узел дерева хранит O(logp){displaystyle O(log p)} бит для записи чисел в нём, можно заключить, что общий размер дерева не превосходит O(log2p){displaystyle O(log ^{2}p)}. Общее время проверки в свою очередь может быть оценено как O(log5p){displaystyle O(log ^{5}p)}, так как нужно сделать O(log4p){displaystyle O(log ^{4}p)} действий в каждом из O(logp){displaystyle O(log p)} узлов.
В то время как сертификаты Пратта полезны в теории и легко проверяются, нахождение сертификата для числа n{displaystyle n} требует факторизации n−1{displaystyle n-1} и прочих потенциально больших чисел. Это просто сделать в некоторых частных случаях, например, для простых чисел Ферма, но в общем случае эта задача сейчас гораздо сложнее обычной проверки числа на простоту.