Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

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

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


 Теорема Прота гласит: Если 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, 2\textsuperscript1 + 1 = 3 кратно 3, поэтому 3 является простым.
  • для p = 5, 3\textsuperscript2 + 1 = 10 кратно 5, поэтому 5 является простым.
  • p = 13, 5\textsuperscript6 + 1 = 15626 делится на 13, 13 является простым.
  • для p = 9, которая не является простым, не существует b таких что a \textsuperscript4 + 1 делится на 9.

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


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

 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769,929, 1153 \ldots
 На май 2017 года, крупнейшее известное простое Прота, 10223 ·2\textsuperscript31172165 + 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 года.