Сертификат первичности

В математике и информатике сертификат простоты или доказательство простоты — это краткое формальное доказательство того, что число простое. Сертификаты простоты позволяют быстро проверить простоту числа без необходимости запуска дорогостоящего или ненадежного теста на простоту . «Краткое» обычно означает, что доказательство должно быть не более чем полиномиально большим, чем количество цифр в самом числе (например, если число имеет b бит, доказательство может содержать примерно b). ² биты).

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

Получить сертификаты для задачи о дополнении, позволяющие установить, что число является составным, несложно: достаточно указать нетривиальный делитель. Стандартные вероятностные тесты на простоту, такие как тест на простоту Бейли-ПСВ , тест на простоту Ферма и тест на простоту Миллера-Рабина, также создают сертификаты составности в случае, если входные данные являются составными, но не создают сертификаты для простых входных данных.

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

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

Теорема Лукаса : предположим, что у нас есть целое число a такое, что:

• а ^{п - 1} ≡ 1 (по модулю n ),
• для каждого простого множителя q числа n − 1 это не тот случай, когда a ^{( п - 1)/ q} ≡ 1 (против n ).

Тогда n простое.

Учитывая такой a (называемый свидетелем ) и разложение на простые множители n - 1, легко быстро проверить вышеуказанные условия: нам нужно всего лишь выполнить линейное количество модульных возведений в степень, поскольку каждое целое число имеет меньше простых множителей, чем битов, и каждое из этих действий можно выполнить путем возведения в степень путем возведения в квадрат умножения O(log n ) (см. обозначение big-O ). Даже при умножении целых чисел в начальной школе это всего лишь O((log n ) ⁴ ) время; используя алгоритм умножения с наиболее известным асимптотическим временем выполнения, созданным Дэвидом Харви и Йорисом ван дер Хувеном, мы можем снизить его до O((log n ) ³ (log log n )) время или с использованием обозначения soft-O Õ((log n ) ³ ).

Однако можно обманом заставить верификатор принять составное число, задав ему «простую факторизацию» n - 1, включающую составные числа. Например, предположим, что мы утверждаем, что n = 85 является простым, предоставляя a = 4 и n - 1 = 6 × 14 в качестве «простой факторизации». Тогда (используя q = 6 и q = 14):

• 4 взаимно просто с 85,
• 4 ⁸⁵⁻¹ ≡ 1 (по модулю 85),
• 4 ^(85−1)/6 ≡ 16 (против 85), 4 ^(85−1)/14 ≡ 16 (против 85).

Мы могли бы ошибочно заключить, что 85 — простое число. Мы не хотим просто заставлять верификатор факторизовать число, поэтому лучший способ избежать этой проблемы — предоставить сертификаты простоты также для каждого из простых множителей n - 1, которые являются лишь меньшими экземплярами исходной проблемы. . Мы продолжаем рекурсивно таким образом, пока не достигнем числа, которое, как известно, является простым, например 2. В конечном итоге мы получаем дерево простых чисел, каждое из которых связано со свидетелем a . Например, вот полный сертификат Пратта на номер 229:

• 229 ( а = 6, 229 − 1 = 2 ²  × 3 × 19),
  • 2 (известное простое число),
  • 3 ( а = 2, 3 − 1 = 2),
    • 2 (известное простое число),
  • 19 ( а = 2, 19 - 1 = 2 × 3 ² ),
    • 2 (известное простое число),
    • 3 ( а = 2, 3 − 1 = 2),
      • 2 (известное простое число).

Можно показать, что это дерево доказательства содержит не более $4\log _{2}n-4$ значения, отличные от 2, простым индуктивным доказательством (основанным на теореме 2 Пратта). Результат справедлив для 3; вообще, возьмите p > 3 и пусть его дочерними элементами в дереве будут p ₁ , ..., p _k . По индуктивному предположению дерево с корнем в точке содержит _pi не более $4\log _{2}p_{i}-4$ значений, поэтому все дерево содержит не более

$1+\sum _{i=1}^{k}(4\log _{2}p_{i}-4)=-4k+4\log _{2}p_{1}\cdots p_{k}\leq 4\log _{2}p-4,$

поскольку k ≥ 2 и p ₁ ... p _k = p - 1. Поскольку каждое значение имеет не более log n бит, это также демонстрирует, что размер сертификата равен O((log n ) ² ) биты.

Поскольку существуют значения O(log n ), отличные от 2, и каждое из них требует не более одного возведения в степень для проверки (а возведение в степень доминирует во времени выполнения), общее время равно O((log n ) ³ (log log n )(log log log n )), или Õ((log n ) ³ ), что вполне осуществимо для чисел в диапазоне, с которым обычно работают теоретики вычислительных чисел.

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

Сертификаты Аткина-Гольдвассера-Килиана-Морена

Чтобы решить проблему эффективной генерации сертификатов для большего числа пользователей, в 1986 году Шафи Голдвассер и Джо Килиан описали новый тип сертификатов, основанный на теории эллиптических кривых . Это, в свою очередь, было использовано AOL Atkin и Франсуа Мораном в качестве основы для сертификатов Аткина-Голдвассера-Килиана-Морена, которые представляют собой тип сертификатов, создаваемых и проверяемых системами проверки простоты эллиптических кривых . Так же, как сертификаты Пратта основаны на теореме Лукаса, сертификаты Аткина-Голдвассера-Килиана-Морена основаны на следующей теореме Гольдвассера и Килиана (лемма 2 из «Почти все простые числа могут быть быстро сертифицированы»):

Теорема : Предположим, нам дано:

• целое положительное число n, не кратное 2 или 3;
• M _x , My _y , A, B в $\mathbb {Z} _{n}$ (целые числа по модулю n ), удовлетворяющие My _y ² = М _х ³ +АМ _х +В и с 4А ³ +27Б ² взаимно прост с n ;
• простое число $q>n^{1/2}+1+2n^{1/4}$.

Тогда M = (M _x , My _y ) — неединичная точка на эллиптической кривой y ² = х ³ + Ax + B. Пусть k M — это M, добавленное к самому себе k раз с использованием стандартного сложения эллиптических кривых. Тогда, если q M — единичный элемент I, то n — простое число.

Технически эллиптическую кривую можно построить только над полем, и $\mathbb {Z} _{n}$ является полем только в том случае, если n простое, поэтому мы, похоже, предполагаем результат, который пытаемся доказать. Трудность возникает в алгоритме сложения эллиптических кривых, который принимает обратные значения в поле, которое может не существовать в $\mathbb {Z} _{n}$. Однако можно показать (лемма 1 из «Почти все простые числа могут быть быстро сертифицированы»), что если мы просто выполняем вычисления так, как будто кривая четко определена, и ни в какой момент не пытаемся инвертировать элемент без обратного, результат все еще действителен; если мы встречаем элемент, не имеющий обратного, это устанавливает, что n является составным.

Чтобы получить сертификат из этой теоремы, мы сначала кодируем M _x , My _, A, B и q , затем рекурсивно кодируем доказательство простоты для q < n , продолжая до тех пор, пока не достигнем известного простого числа. Этот сертификат имеет размер O((log n ) ² ) и может быть проверено за O((log n ) ⁴ ) время. Более того, можно показать, что алгоритм, генерирующий эти сертификаты, требует полиномиального времени для всех, кроме небольшой доли простых чисел, и эта доля экспоненциально уменьшается с размером простых чисел. Следовательно, он хорошо подходит для генерации сертифицированных больших случайных простых чисел, что важно в криптографических приложениях, таких как генерация доказуемо действительных ключей RSA .

Сертификаты Поклингтона

Доказуемая генерация простых чисел на основе вариантов теоремы Поклингтона (см. тест на простоту Поклингтона ) могут быть эффективными методами генерации простых чисел (затраты обычно меньше, чем вероятностная генерация) с дополнительным преимуществом встроенных сертификатов простоты. Хотя это может показаться особым простым числом, обратите внимание, что каждое простое целое число может быть сгенерировано с помощью доказуемого алгоритма генерации, основанного на Поклингтоне.

Тесты на простоту Поклингтона

Позволять $P=Rh+1$ где $R=\prod q_{j}^{e_{j}}$ где $q_{j}$ являются различными простыми числами с $e_{j}$ целое число больше нуля и свидетель $g$ такой, что:

1. $g^{Rh}\equiv 1{\bmod {P}}$ ( 1 )

2. $\gcd((g^{Rh/q_{j}}-1{\bmod {P}}),P)=1$ для всех $q_{j}$. ( 2 )

Тогда P является простым, если выполняется одно из следующих условий:

а) (см. ) $R\geq h$ или эквивалентно $R>P^{1/2}$ ( а )

б) (см. ) $R\geq h^{1/2}$ или эквивалентно $R>P^{1/3}$ и

• с ${\begin{array}{lr}a\equiv h{\bmod {R}}&0\leq a<R\\b=(h-a)/R\end{array}}$,
• такой, что $(a-4b)\neq 0$ и существует маленькое простое число $r>2$ такой, что $(a-4b)^{r/2}\neq 1{\bmod {r}}$.

( б )

Сертификат примата Поклингтона

Сертификат простоты Поклингтона состоит из простого числа P, набора простых чисел $q_{j}$ разделяющий $(P-1)$, каждый со своим собственным сертификатом простого числа Поклингтона или достаточно маленьким, чтобы быть известным простым числом, и свидетелем $g$.

Биты, необходимые для этого сертификата (и порядок вычислительных затрат), должны варьироваться примерно от $\log _{2}{P}\left(1+\sum _{k=1}^{\infty }{\frac {1}{3^{k}}}\right)=1.5\log _{2}{P}$ для версии ( b ) до $\log _{2}{P}\left(1+\sum _{k=1}^{\infty }{\frac {1}{2^{k}}}\right)=2\log _{2}{P}$ для версии ( а )

Небольшой пример

Позволять $P=1056893$. Обратите внимание, что $(P-1)=1621\cdot 163\cdot 2^{2}$ и $P^{1/2}=1028.053\ldots$, $P^{1/3}=101.86156\ldots$.

• Используя «свидетеля» 2, уравнение 1 удовлетворяется, а уравнение 2 — с использованием $q=163$ и $q=1621$.
• Для версии a сертификат нужен только $P=1056893,\ q=1621,\ g=2$.
• для версии b сертификат нужен только $P=1056893,\ q=163,\ g=2$, но осталось еще немного поработать:
  • $h=(1056893-1)/163=6484$
  • $a\equiv h\equiv 127{\bmod {163}}$ и $b=\left(6484-127\right)/163=39$
  • С использованием $r=3$ терпит неудачу: $\left(127^{2}-4\cdot 39\right)^{(3-1)/2}\equiv (1^{2}-0)^{1}\equiv 1{\bmod {3}}$
  • С использованием $r=5$ удается: $\left(127^{2}-4\cdot 39\right)^{(5-1)/2}\equiv (2^{2}-1)^{2}\equiv 2{\bmod {5}}$, и $P$ является простым.

Влияние «ПРАЙМС находится в P»

«ПРАЙМС находится в P» стал прорывом в теоретической информатике. Эта статья, опубликованная Маниндрой Агравалом , Нитином Саксеной и Нираджем Каялом в августе 2002 года, доказывает, что знаменитая проблема проверки простоты числа может быть решена детерминированно за полиномиальное время. авторы получили премию Гёделя 2006 г. и премию Фулкерсона За эту работу 2006 г.

Поскольку тестирование на простоту теперь можно проводить детерминированно за полиномиальное время с помощью теста на простоту AKS , простое число само по себе может рассматриваться как сертификат своей собственной простоты. Этот тест выполняется за Õ((log n ) ⁶ ) время. На практике этот метод проверки дороже, чем проверка сертификатов Пратта, но не требует каких-либо вычислений для определения самого сертификата.

Внешние ссылки

• Mathworld: Сертификат первичности
• Mathworld: Сертификат Пратта
• Mathworld: Сертификат Аткина-Голдвассера-Килиана-Морена
• Главный глоссарий: Сертификат первичности
• Вашек Хватал . Конспект лекций по доказательствам простоты Пратта . Департамент компьютерных наук. Университет Рутгерса. PDF-версия в Университете Конкордия .