В математике и информатике сертификат простоты — это строгое доказательство того, что число является простым . Наличие сертификата простоты позволяет проверить, что число простое, не прибегая к тестам простоты .

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

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

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

Сертификат Пратта

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

(Теорема Люка) Число ${\displaystyle p}$ является простым тогда и только тогда когда в кольце остатков по модулю ${\displaystyle p}$ существует элемент ${\displaystyle a\in \mathbb {Z} _{p}}$ такой что:

1. ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$ ,
2. ${\displaystyle a^{\frac {p-1}{q}}\not \equiv 1{\pmod {p}}}$ для всех простых чисел ${\displaystyle q}$ , которые делят ${\displaystyle p-1}$ .

Имея такое число ${\displaystyle a}$ (называемое свидетелем простоты ) и разбиение ${\displaystyle p-1}$ на простые сомножители, можно быстро проверить приведённые условия — нужно выполнить ${\displaystyle O(\log p)}$ возведений в степень по модулю, что может быть сделано за ${\displaystyle O(\log p)}$ умножений с помощью двоичного возведения в степень . Сами же умножения в наивной реализации («в столбик») выполняются за ${\displaystyle O(\log ^{2}p)}$ , что даёт общую оценку времени работы в ${\displaystyle O(\log ^{4}p)}$ .

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

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

В то время как сертификаты Пратта полезны в теории и легко проверяются, нахождение сертификата для числа ${\displaystyle n}$ требует факторизации ${\displaystyle n-1}$ и прочих потенциально больших чисел. Это просто сделать в некоторых частных случаях, например, для простых чисел Ферма , но в общем случае эта задача сейчас гораздо сложнее обычной проверки числа на простоту.

Влияние на «PRIMES is in P»

Статья «PRIMES is in P» стала прорывом в теоретической информатике . В этой статье, опубликованной Маниндрой Агравалом и его двумя студентами Нираджем Каялом и Нитином Саксеной в августе 2002 г., доказывается, что знаменитая задача проверки числа на простоту может быть детерминированно решена за полиномиальное время. Авторы стали лауреатами премии Гёделя , которая составляет $5000 и премии Фалкерсона 2006 года за свою работу.

В силу того, что проверка простоты теперь может проведена за полиномиальное время с помощью теста AKS , простое число может рассматриваться как сертификат своей собственной простоты. Данный тест выполняется за время ${\displaystyle {\tilde {O}}(\log ^{6}n)}$ , что делает такую проверку более затратной, чем с помощью сертификата Пратта, однако не требует нахождения самого сертификата.

Примечания

Ссылки

• . . Department of Computer Science. Rutgers University. .