Введение
В математике и информатике, сертификат простоты или доказательство простоты — это лаконичное, формальное доказательство того, что число является простым. Сертификаты простоты позволяют быстро проверить простоту числа, не прибегая к дорогостоящему или ненадежному тесту простоты. "Лаконичность" обычно означает, что доказательство должно быть не более чем полиномиально больше, чем количество цифр в самом числе (например, если число имеет b битов, доказательство может содержать примерно b² битов). Сертификаты простоты напрямую приводят к доказательствам того, что такие задачи, как проверка простоты и дополнение к задаче факторизации целых чисел, принадлежат классу NP — классу задач, которые могут быть проверены за полиномиальное время при наличии решения. Эти задачи уже тривиально принадлежат классу co-NP. Это было первым серьезным свидетельством того, что эти задачи не являются NP-полными, поскольку в противном случае это означало бы, что NP является подмножеством co-NP, что общепризнанно ложным утверждением; фактически, это была первая демонстрация задачи, принадлежащей пересечению NP и co-NP, которая в то время не была известна как задача из класса P.
Создание сертификатов для дополнительной задачи, чтобы установить, что число составное, — просто: достаточно предоставить нетривиальный делитель. Стандартные вероятностные тесты простоты, такие как тест простоты Baillie–PSW, тест простоты Ферма и тест простоты Миллера – Рабина, также генерируют сертификаты составности в случае, когда входное число составное, но не генерируют сертификаты для простых чисел.
Сертификаты на основе Pocklington
Доказательная генерация простых чисел, основанная на вариантах теоремы Поклинтона (см. тест на простоту Поклинтона), может быть эффективным способом генерации простых чисел (стоимость обычно ниже, чем при вероятностной генерации) с дополнительным преимуществом в виде встроенных сертификатов простоты. Несмотря на то, что это могут показаться особые простые числа, следует отметить, что любое простое число может быть сгенерировано с помощью алгоритма доказательной генерации на основе теоремы Поклинтона.
Влияние "PRIMES находится в P"
"PRIMES в P" стал прорывом в теоретической информатике. Эта статья, опубликованная Маниндрой Агравалом, Нитином Саксеной и Ниражем Кайалом в августе 2002 года, доказывает, что известная проблема проверки простоты числа может быть решена детерминированно за полиномиальное время. Авторы получили премию Гёделя 2006 года и премию Фулкерсона 2006 года за эту работу. Поскольку проверка простоты теперь может быть выполнена детерминированно за полиномиальное время с использованием теста простоты AKS, простое число само по себе может рассматриваться как сертификат своей простоты. Этот тест выполняется за время Õ((log n)6). На практике этот метод проверки более затратен, чем проверка сертификатов Пратта, но не требует каких-либо вычислений для получения самого сертификата.