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

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

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

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

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

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

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

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

потом п простое.

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

Однако можно обманом заставить проверяющего принять составное число, задав ему «разложение на простые множители» п - 1, который включает составные числа. Например, предположим, что мы утверждаем, что п = 85 - простое число, обеспечивающее а = 4 и п - 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 - простое число. Мы не хотим просто заставлять верификатор множить число, поэтому лучший способ избежать этой проблемы - предоставить сертификаты примитивности для каждого из основных множителей п - 1, которые представляют собой лишь меньшие экземпляры исходной проблемы. Мы продолжаем рекурсивно таким образом, пока не достигнем числа, известного как простое, например 2. В итоге мы получим дерево простых чисел, каждое из которых связано со свидетелем. а. Например, вот полный сертификат 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 (известное простое число).

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

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

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

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

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

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

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

Теорема: Допустим, нам даны:

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

Тогда M = (M_Икс, М_у) - нетождественная точка на эллиптической кривой у² = Икс³ + Ax + B. Пусть kМ быть М добавлено к себе k раз, используя стандартное сложение эллиптических кривых. Тогда, если qM - единичный элемент I, тогда п простое.

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

Чтобы получить свидетельство из этой теоремы, мы сначала кодируем M_Икс, М_у, Группа q, затем рекурсивно закодировать доказательство простоты для q < п, продолжая, пока не достигнем известного пика. Этот сертификат имеет размер O ((log п)²) и проверяется в O ((log п)⁴) время. Более того, можно показать, что алгоритм, который генерирует эти сертификаты, работает за полиномиальное время для всех простых чисел, кроме небольшой, и эта доля экспоненциально уменьшается с размером простых чисел. Следовательно, он хорошо подходит для генерации сертифицированных больших случайных простых чисел, что важно для криптография такие приложения, как создание доказуемо действительных ЮАР ключи.

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

"ПРИМЕРЫ находится в P"^[4] был прорывом в теоретической информатике. Эта статья, опубликованная Маниндра Агравал, Нитин Саксена, и Нирадж Каял в августе 2002 г., доказывает, что известная проблема проверки простоты числа может быть решена детерминированно за полиномиальное время. Авторы получили 2006 г. Премия Гёделя и 2006 г. Премия Фулкерсона для этой работы.

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

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

1. Воан Пратт. «У каждого прайма есть емкий сертификат». SIAM Журнал по вычислениям, т. 4. С. 214–220. 1975 г. Цитаты, Полный текст.
2. Гольдвассер, С. и Килиан, Дж. «Почти все простые числа могут быть быстро сертифицированы». Proc. 18-й STOC. С. 316–329, 1986. Полный текст.
3. Аткин, А.; Морейн, Ф. (1993). «Эллиптические кривые и доказательство простоты» (PDF). Математика вычислений. 61 (203): 29–68. Дои:10.1090 / с0025-5718-1993-1199989-х. JSTOR  2152935. МИСТЕР  1199989.
4. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (Сентябрь 2004 г.). "ПРИМЕРЫ находится в P" (PDF). Анналы математики. 160 (2): 781–793. Дои:10.4007 / анналы.2004.160.781. JSTOR  3597229. МИСТЕР  2123939.

внешняя ссылка

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