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

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

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

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

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

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

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

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 ) (log log log n )) времени, или используя обозначение soft-O Õ ((журнал п ) ³ ).

Однако можно обманом заставить проверяющего принять составное число, задав ему «разложение на простые множители» 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 . Например, вот полный сертификат Pratt на номер 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 Пратта). Результат верен для 3; в общем, возьмем p > 3 и пусть его дочерними элементами в дереве будут p ₁ , ..., p _k . По предположению индукции, дерево с корнем p _i содержит не более значений, поэтому все дерево содержит не более ${\ Displaystyle 4 \ журнал _ {2} п-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 ) ³ ), что вполне возможно для чисел в диапазоне, с которым обычно работают теоретики вычислительных чисел.

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

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

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

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

положительное целое число n, не делимое на 2 или 3;
M _x , M _y , A, B в (целые числа по модулю n ), удовлетворяющие M _y² = M _x³ + AM _x + B и с 4A ³ + 27B ^2, взаимно простыми с n ; ${\ Displaystyle \ mathbb {Z} _ {п}}$
прайм . ${\ 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} _ {п}}$ ${\ Displaystyle \ mathbb {Z} _ {п}}$

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

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

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

Тесты поклингтона на примитивность

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

1.

{\ Displaystyle г ^ {Rh} \ эквив 1 {\ bmod {P}}}

( 1 )

2. для всех .

{\ displaystyle \ gcd ((g ^ {Rh / q_ {j}} - 1 {\ bmod {P}}), P) = 1}

{\ displaystyle q_ {j}}

( 2 )

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

а) (см.) или эквивалентно

{\ displaystyle R \ geq h}

{\ displaystyle R> P ^ {1/2}}

( )

б) (см.) или эквивалентным образом и

{\ displaystyle R \ geq h ^ {1/2}}

{\ displaystyle R> P ^ {1/3}}

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

( б )

Сертификат Pocklington Primality

Сертификат на простоту Pocklington состоит из простого 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 \ журнал _ {2} {P}}$ ${\ displaystyle \ log _ {2} {P} \ left (1+ \ sum _ {k = 1} ^ {\ infty} {\ frac {1} {2 ^ {k}}} \ right) = 2 \ журнал _ {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 P = 1056893, \ q = 163, \ g = 2}$
- ${\ displaystyle h = (1056893-1) / 163 = 6484}$
- ${\ Displaystyle а \ эквив ч \ эквив 127 {\ bmod {163}}}$ и ${\ displaystyle b = \ left (6484-127 \ right) / 163 = 39}$
- Использование не удается: ${\ displaystyle r = 3}$ ${\ Displaystyle \ влево (127 ^ {2} -4 \ cdot 39 \ right) ^ {(3-1) / 2} \ эквив (1 ^ {2} -0) ^ {1} \ эквив 1 {\ bmod {3}}}$
- Успешное использование :, и простое. ${\ displaystyle r = 5}$ ${\ Displaystyle \ влево (127 ^ {2} -4 \ cdot 39 \ right) ^ {(5-1) / 2} \ эквив (2 ^ {2} -1) ^ {2} \ эквив 2 {\ bmod {5}}}$ ${\ displaystyle P}$

Влияние «ПРИМЕР в П»

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

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

использованная литература

^ Воан Пратт. «У каждого прайма есть емкий сертификат». SIAM Journal on Computing , vol. 4. С. 214–220. 1975. Цитаты , Полнотекстовый .
^ Голдвассер, С. и Килиан, Дж. «Почти все простые числа могут быть быстро сертифицированы». Proc. 18-й STOC. С. 316–329, 1986. Полный текст .
^ Аткин, О.Л . ; Морейн, Ф. (1993). «Эллиптические кривые и доказательство простоты» (PDF) . Математика вычислений . 61 (203): 29–68. DOI : 10.1090 / s0025-5718-1993-1199989-х . JSTOR 2152935 . Руководство по ремонту 1199989 .
^ Поклингтон, Генри К. (1914–1916). «Определение простого или составного характера больших чисел по теореме Ферма». Труды Кембриджского философского общества . 18 : 29–30.
^ Crandall, Ричард; Померанс, Карл. «Простые числа: вычислительная перспектива» (2-е изд.). "Springer-Verlag, 175 Fifth Ave, New York, New York 10010, USA, 2005".
^ Бриллхарт, Джон ; Lehmer, DH ; Селфридж, Дж. Л. (апрель 1975 г.). «Новые критерии первичности и факторизации 2 ^м ± 1» (PDF) . Математика вычислений . 29 (130): 620–647. DOI : 10.1090 / S0025-5718-1975-0384673-1 . JSTOR 2005583 .
^ Агравал, Маниндра ; Каял, Нирадж ; Саксена, Нитин (сентябрь 2004 г.). «ПРИМЕР в П» (PDF) . Анналы математики . 160 (2): 781–793. DOI : 10.4007 / анналы.2004.160.781 . JSTOR 3597229 . Руководство по ремонту 2123939 .

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

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

[1] Воан Пратт. «У каждого прайма есть емкий сертификат». SIAM Journal on Computing , vol. 4. С. 214–220. 1975. Цитаты , Полнотекстовый .

[2] Голдвассер, С. и Килиан, Дж. «Почти все простые числа могут быть быстро сертифицированы». Proc. 18-й STOC. С. 316–329, 1986. Полный текст .

[atkin-morain-3] Аткин, О.Л . ; Морейн, Ф. (1993). «Эллиптические кривые и доказательство простоты» (PDF) . Математика вычислений . 61 (203): 29–68. DOI : 10.1090 / s0025-5718-1993-1199989-х . JSTOR 2152935 . Руководство по ремонту 1199989 .

[Pocklington-4] Поклингтон, Генри К. (1914–1916). «Определение простого или составного характера больших чисел по теореме Ферма». Труды Кембриджского философского общества . 18 : 29–30.

[Primes-5] Crandall, Ричард; Померанс, Карл. «Простые числа: вычислительная перспектива» (2-е изд.). "Springer-Verlag, 175 Fifth Ave, New York, New York 10010, USA, 2005".

[BLS75-6] Бриллхарт, Джон ; Lehmer, DH ; Селфридж, Дж. Л. (апрель 1975 г.). «Новые критерии первичности и факторизации 2 ^м ± 1» (PDF) . Математика вычислений . 29 (130): 620–647. DOI : 10.1090 / S0025-5718-1975-0384673-1 . JSTOR 2005583 .

[AKS-7] Агравал, Маниндра ; Каял, Нирадж ; Саксена, Нитин (сентябрь 2004 г.). «ПРИМЕР в П» (PDF) . Анналы математики . 160 (2): 781–793. DOI : 10.4007 / анналы.2004.160.781 . JSTOR 3597229 . Руководство по ремонту 2123939 .

Languages

In other projects