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

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

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

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

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

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

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

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

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

Учитывая такой a (называемый свидетелем ) и разложение на простые множители n  - 1, легко быстро проверить вышеуказанные условия: нам нужно всего лишь выполнить линейное количество модульных возведений в степень, поскольку каждое целое число имеет меньше простых множителей, чем битов, и каждое из этих действий можно выполнить путем возведения в степень путем возведения в квадрат умножения O(log n ) (см. обозначение big-O ). Даже при умножении целых чисел в начальной школе это занимает всего O((log n ) ⁴ ) времени; используя алгоритм умножения с наиболее известным асимптотическим временем выполнения, алгоритм Шёнхаге – Штрассена , мы можем снизить это время до O((log n ) ³ (log log n )(log 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 (известное простое число).

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

${\displaystyle 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 году Шафи Голдвассер и Джо Килиан описали новый тип сертификатов, основанный на теории эллиптических кривых . ^[2] Это, в свою очередь, было использовано AOL Аткином и Франсуа Мореном в качестве основы для сертификатов Аткина-Голдвассера-Килиана-Морена, которые представляют собой тип сертификатов, генерируемых и проверяемых системами проверки простоты эллиптических кривых . ^[3] Так же, как сертификаты Пратта основаны на теореме Лукаса, сертификаты Аткина-Голдвассера-Килиана-Морена основаны на следующей теореме Гольдвассера и Килиана (лемма 2 из «Почти все простые числа могут быть быстро сертифицированы»):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

1. Воан Пратт. «У каждого простого числа есть краткий сертификат». SIAM Journal on Computing , том. 4, стр. 214–220. 1975. Цитаты, полный текст.
2. Гольдвассер С. и Килиан Дж. «Почти все простые числа можно быстро сертифицировать». Учеб. 18-й СТОК. С. 316–329, 1986. Полный текст.
3. Аткин, ПР ; Морейн, Ф. (1993). «Эллиптические кривые и доказательство простоты» (PDF) . Математика вычислений . 61 (203): 29–68. Бибкод : 1993MaCom..61...29A. дои : 10.1090/s0025-5718-1993-1199989-x . JSTOR  2152935. MR  1199989.
4. Поклингтон, Генри К. (1914–1916). «Определение простой или составной природы больших чисел по теореме Ферма». Труды Кембриджского философского общества . 18 :29–30.
5. Крэндалл, Ричард; Померанс, Карл. «Простые числа: вычислительная перспектива» (2-е изд.). Спрингер-Верлаг, Пятая авеню, 175, Нью-Йорк, Нью-Йорк 10010, США, 2005 г.
6. Бриллхарт, Джон ; Лемер, ДХ ; Селфридж, Дж. Л. (апрель 1975 г.). «Новые критерии простоты и факторизация 2m ± 1» (PDF) . Математика вычислений . 29 (130): 620–647. doi : 10.1090/S0025-5718-1975-0384673-1 . JSTOR  2005583.
7. Агравал, Маниндра ; Каял, Нирадж ; Саксена, Нитин (сентябрь 2004 г.). «ПРАЙМС находится в P» (PDF) . Анналы математики . 160 (2): 781–793. дои : 10.4007/анналы.2004.160.781 . JSTOR  3597229. MR  2123939.

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

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