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

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

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

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

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

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

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

• а ^{n − 1} ≡ 1 (mod n ),
• для каждого простого множителя 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 )) или используя обозначение 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 . По индуктивной гипотезе, дерево с корнем в p _i содержит не более значений, поэтому все дерево содержит не более ${\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 , M _y , A, B in (целые числа по модулю n ), удовлетворяющие M _y ² = M _x ³ + AM _x + B и где 4A ³ + 27B ² взаимно просты с n ; ${\displaystyle \mathbb {Z} _{n}}$
• простое число . ${\displaystyle q>n^{1/2}+1+2n^{1/4}}$

Тогда M = (M _x , M _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 , M _y , 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}}}$
  • Использование успешно: и является простым. ${\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}$

Влияние «PRIMES находится в P»

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

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

Ссылки

1. Воан Пратт. «Каждое простое число имеет краткое свидетельство». Журнал SIAM по вычислениям , т. 4, стр. 214–220. 1975. Цитаты, полный текст.
2. Голдвассер, С. и Килиан, Дж. «Почти все простые числа могут быть быстро сертифицированы». Proc. 18th STOC. стр. 316–329, 1986. Полный текст.
3. Аткин, А. О. Л .; Морейн, Ф. (1993). «Эллиптические кривые и доказательство простоты» (PDF) . Математика вычислений . 61 (203): 29–68. Bibcode : 1993MaCom..61...29A. doi : 10.1090/s0025-5718-1993-1199989-x . JSTOR  2152935. MR  1199989.
4. Поклингтон, Генри К. (1914–1916). «Определение простой или составной природы больших чисел теоремой Ферма». Труды Кембриджского философского общества . 18 : 29–30.
5. Крэндалл, Ричард; Померанс, Карл. «Простые числа: вычислительная перспектива» (2-е изд.). Springer-Verlag, 175 Fifth Ave, New York, Нью-Йорк 10010, США, 2005.
6. Brillhart, John ; Lehmer, DH ; Selfridge, JL (апрель 1975 г.). "Новые критерии простоты и факторизации 2m ± 1" (PDF) . Mathematics of Computation . 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: Сертификат Аткина-Гольдвассера-Килиана-Морена
• The Prime Glossary: ​​Сертификат первичности
• Вашек Хватал . Конспект лекций по доказательствам простоты Пратта. Кафедра компьютерных наук. Ратгерский университет. PDF-версия в Университете Конкордия.