WikiSort.ru - Не сортированное

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

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

Теорема Прота гласит:

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

(а) Пусть p — простое. Тогда для любого квадратичного невычета a: ${\displaystyle a^{(p-1)/2}\equiv -1{\pmod {p}}}$ по критерию Эйлера.

(б) Пусть ${\displaystyle a^{(p-1)/2}\equiv -1{\pmod {p}}}$ для некоторого квадратичного невычета a. Используем критерий Поклингтона, где ${\displaystyle n=2^{k}+1}$ . Тогда ${\displaystyle q=2}$  — единственный простой делитель ${\displaystyle n-1}$ . Проверим выполнение условий критерия:

1. ${\displaystyle a^{n-1}=(a^{(n-1)/2})^{2}\equiv 1{\pmod {n}}}$  — выполнено.
2. числа n и ${\displaystyle a^{(n-1)/q}-1}$ взаимно просты — выполнено.

Так как условие ${\displaystyle 2^{k}>{\sqrt {n}}-1}$ выполнено, n — простое. ^[1]

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

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

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

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

Примеры

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

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

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

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 … (последовательность A080076 в OEIS)

На май 2017 года, крупнейшее известное простое Прота, 10223 · 2^31172165 + 1, найдено проектом Primegrid. Оно имеет 9383761 десятичных цифр и является крупнейшим известным простым, не являющимся простым Мерсенна.^[3]

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

Лемма. Пусть ${\displaystyle n=l^{k}}$ для некоторого простого l и ${\displaystyle k\geqslant 1}$ . Пусть ${\displaystyle r^{e}}$  — степень простого числа, где ${\displaystyle r\neq l}$ . Если ${\displaystyle r^{e}{\mathcal {j}}\phi (n)}$ и ${\displaystyle r^{e}>{\sqrt {n}}}$ , то n — простое.

Доказательство. ${\displaystyle r^{e}}$  — делитель ${\displaystyle \phi (n)=(l-1)l^{k-1}}$ , поэтому ${\displaystyle r^{e}{\mathcal {j}}l-1}$ . Если ${\displaystyle k>1}$ , то ${\displaystyle \phi (n)\geqslant (l-1)l>r^{2}e>n}$  — противоречие. Следовательно ${\displaystyle k=1}$ и ${\displaystyle n}$  — простое.

Теорема (обобщенная теорема Прота). Пусть ${\displaystyle N=r^{e}t+1}$ для некоторого простого ${\displaystyle r}$ и целых ${\displaystyle e,t\geqslant 1}$ . Пусть ${\displaystyle r^{e}>t}$ . Если ${\displaystyle a^{N-1}\equiv 1(modN)}$ и ${\displaystyle a^{(N-1)/r}\not \equiv 1(modN)}$ для некоторого целого ${\displaystyle a}$ , то ${\displaystyle N}$  — простое.

Доказательство обобщенной теоремы можно найти в работе Sze^[4].

История

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

См. также

• Число Серпинского

Примечания

Ссылки

• Weisstein, Eric W. Proth's Theorem (англ.) на сайте Wolfram MathWorld.
• «Обзор проверок на простоту», Кучин, 2005
• Sze, T.W. On Solving Univariate Polynomial Equations Over Finite Fields and Some Related Problems. — University of Maryland, College Park, 2007. — ISBN 9780549451037.