Теорема Прота

 В теории чисел теорема Прота является тестом простоты для чисел Прота.

Формулировка


 Теорема Прота гласит: Если p — это число Прота вида k2n+1, где k — нечётно и k<2n, то p — простое (называемое простым Прота) тогда и только тогда, когда для некоторого квадратичного невычета a выполняется сравнение:

a(p1)/21(modp)

Доказательство


(а) Пусть p — простое. Тогда для любого квадратичного невычета a: a(p1)/21(modp) по критерию Эйлера.
(б) Пусть a(p1)/21(modp) для некоторого квадратичного невычета a. Используем критерий Поклингтона, где n=2k+1 . Тогда q=2 — единственный простой делитель n1. Проверим выполнение условий критерия:

  1. an1=(a(n1)/2)21(modn) — выполнено.
  2. числа n и a(n1)/q1 взаимно просты — выполнено.

 Так как условие 2k>n1 выполнено, n — простое.

Тестирование чисел Прота на простоту


 Теорема Прота может быть использована для тестирования простоты чисел Прота. Алгоритм вероятностного теста, основанного на теореме, выглядит следующим образом: Случайным образом выбирается целое число a, такое что a1(modN)$ивычисляетb \equiv a^{(N-1)/2} \pmod{N}\$. Возможны следующие исходы:

  1. b1(modN)$,тогдаN$ — простое по теорема Прота.
  2. b±1(modN)$иb^2 \equiv 1 \pmod{N}\,тогдаNсоставное,таккакgcd (b \pm 1, N)нетривиальныеделителиN$.
  3. $b^2 \not \equiv 1 \pmod{N}\$, тогда N — составное по малой теореме Ферма.
  4. $b \equiv 1 \pmod{N}\$, тогда результат теста неизвестен.

 Исход (4) является причиной того, что тест вероятностный. В случае (1) a — квадратичный невычет по модулю N. Процедура повторяется пока простота N не будет установлена. Если N — простое, то тест с вероятностью 1/2 подтвердит это за одну итерацию, так как количество квадратичных невычетов по модулю N ровно (N1)/2.

Примеры



  • для p = 3, 21 + 1 = 3 кратно 3, поэтому 3 является простым.
  • для p = 5, 32 + 1 = 10 кратно 5, поэтому 5 является простым.
  • p = 13, 56 + 1 = 15626 делится на 13, 13 является простым.
  • для p = 9, которая не является простым, не существует b таких что a 4 + 1 делится на 9.

Простые числа Прота


 Простые числа Прота образуют последовательность:

  3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 \ldots
  На май 2017 года, крупнейшее известное простое Прота, 10223 · 231172165 + 1, найдено проектом Primegrid. Оно имеет 9383761 десятичных цифр и является крупнейшим известным простым, не являющимся простым Мерсенна.

Обобщенная теорема Прота


Лемма. Пусть n=lk для некоторого простого l и k1. Пусть re — степень простого числа, где rl. Если rejϕ(n) и re>n, то n — простое.

Доказательство. re — делитель ϕ(n)=(l1)lk1, поэтому rejl1. Если k>1, то ϕ(n)(l1)l>r2e>n — противоречие. Следовательно k=1 и n — простое.
Теорема (обобщенная теорема Прота). Пусть N=ret+1 для некоторого простого r и целых e,t1. Пусть re>t. Если aN11(modN) и a(N1)/r1(modN) для некоторого целого a, то N — простое.
 Доказательство обобщенной теоремы можно найти в работе Sze.

История


 (1852—1879) опубликовал теорему около 1878 года.