Сертификат простоты

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

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

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

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

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

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

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

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

Доказательство

Записанные условия в точности значат, что порядок элемента $a$ равен $p-1$.

1. Если такой элемент существует, то хотя бы $p-1$ элементов кольца остатков по модулю $p$ обратимы, то есть, взаимно просты с $p$. Таким образом, все числа $1,2,\dots ,p-1$ взаимно просты с $p$, из чего следует простота этого числа.
2. Если число $p$ простое, то в кольце остатков по модулю $p$ есть первообразный корень, порядок которого обязан быть равен $p-1$.■

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

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

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

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

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

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

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

Ссылки

• Mathworld: Primality Certificate
• Mathworld: Pratt Certificate
• Mathworld: Atkin-Goldwasser-Kilian-Morain Certificate
• Vašek Chvátal. Lecture notes on Pratt’s Primality Proofs. Department of Computer Science. Rutgers University. PDF version at Concordia University.