Теорема Прота
В теории чисел теорема Прота является тестом простоты для чисел Прота.
Формулировка
Теорема Прота гласит:
Если p — это число Прота вида [math]\displaystyle{ k\cdot 2^n + 1 }[/math], где k — нечётно и [math]\displaystyle{ k \lt 2^n }[/math], то p — простое (называемое простым Прота) тогда и только тогда, когда для некоторого квадратичного невычета a выполняется сравнение:
|
Доказательство
(а) Пусть p — простое. Тогда для любого квадратичного невычета a: [math]\displaystyle{ a^{(p-1)/2}\equiv -1 \pmod{p} }[/math] по критерию Эйлера.
(б) Пусть [math]\displaystyle{ a^{(p-1)/2}\equiv -1 \pmod{p} }[/math] для некоторого квадратичного невычета a. Используем критерий Поклингтона, где [math]\displaystyle{ n=2^k+1 }[/math] . Тогда [math]\displaystyle{ q=2 }[/math] — единственный простой делитель [math]\displaystyle{ n-1 }[/math]. Проверим выполнение условий критерия:
- [math]\displaystyle{ a^{n-1} =(a^{(n-1)/2})^2 \equiv 1 \pmod n }[/math] — выполнено.
- числа n и [math]\displaystyle{ a^{(n-1)/q} -1 }[/math] взаимно просты — выполнено.
Так как условие [math]\displaystyle{ 2^k \gt \sqrt {n} -1 }[/math] выполнено, n — простое. [1]
Тестирование чисел Прота на простоту
Теорема Прота может быть использована для тестирования простоты чисел Прота. Алгоритм вероятностного теста, основанного на теореме, выглядит следующим образом: Случайным образом выбирается целое число [math]\displaystyle{ a }[/math], такое что [math]\displaystyle{ a \not \equiv 1 \pmod{p}\ }[/math] и вычисляет [math]\displaystyle{ b \equiv a^{(p-1)/2} \pmod{p}\ }[/math]. Возможны следующие исходы:
- [math]\displaystyle{ b \equiv -1 \pmod{p}\ }[/math], тогда [math]\displaystyle{ p }[/math] — простое по теорема Прота.
- [math]\displaystyle{ b \not \equiv \pm 1 \pmod{p}\ }[/math] и [math]\displaystyle{ b^2 \equiv 1 \pmod{p}\ }[/math], тогда [math]\displaystyle{ p }[/math] — составное, так как [math]\displaystyle{ gcd (b \pm 1, p) }[/math] — нетривиальные делители [math]\displaystyle{ p }[/math].
- [math]\displaystyle{ b^2 \not \equiv 1 \pmod{p}\ }[/math], тогда p — составное по малой теореме Ферма.
- [math]\displaystyle{ b \equiv 1 \pmod{p}\ }[/math], тогда результат теста неизвестен.
Исход (4) является причиной того, что тест вероятностный. В случае (1) [math]\displaystyle{ a }[/math] — квадратичный невычет по модулю [math]\displaystyle{ p }[/math]. Процедура повторяется пока простота [math]\displaystyle{ p }[/math] не будет установлена. Если [math]\displaystyle{ p }[/math] — простое, то тест с вероятностью [math]\displaystyle{ 1/2 }[/math] подтвердит это за одну итерацию, так как количество квадратичных невычетов по модулю [math]\displaystyle{ p }[/math] ровно [math]\displaystyle{ (p-1)/2 }[/math]. [2]
Примеры
- для p = 3, 2 1 + 1 = 3 кратно 3, поэтому 3 является простым.
- для p = 5, 3 2 + 1 = 10 кратно 5, поэтому 5 является простым.
- p = 13, 5 6 + 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 … (последовательность A080076 в OEIS)
На май 2017 года, крупнейшее известное простое Прота, 10223 · 231172165 + 1, найдено проектом Primegrid. Оно имеет 9383761 десятичных цифр и является крупнейшим известным простым, не являющимся простым Мерсенна.[3]
Обобщенная теорема Прота
Лемма. Пусть [math]\displaystyle{ n = l^k }[/math] для некоторого простого l и [math]\displaystyle{ k \geqslant 1 }[/math]. Пусть [math]\displaystyle{ r^e }[/math] — степень простого числа, где [math]\displaystyle{ r \ne l }[/math]. Если [math]\displaystyle{ r^e \mathcal {j} \phi(n) }[/math] и [math]\displaystyle{ r^e\gt \sqrt n }[/math], то n — простое.
- Доказательство. [math]\displaystyle{ r^e }[/math] — делитель [math]\displaystyle{ \phi(n) = (l-1) l ^ {k-1} }[/math], поэтому [math]\displaystyle{ r^e \mathcal {j} l -1 }[/math]. Если [math]\displaystyle{ k \gt 1 }[/math], то [math]\displaystyle{ \phi(n) \geqslant (l-1)l \gt r^2e \gt n }[/math] — противоречие. Следовательно [math]\displaystyle{ k = 1 }[/math] и [math]\displaystyle{ n }[/math] — простое.
Теорема (обобщенная теорема Прота). Пусть [math]\displaystyle{ N=r^{e}t + 1 }[/math] для некоторого простого [math]\displaystyle{ r }[/math] и целых [math]\displaystyle{ e,t\geqslant 1 }[/math]. Пусть [math]\displaystyle{ r^e \gt t }[/math]. Если [math]\displaystyle{ a^{N-1} \equiv 1 (mod N) }[/math] и [math]\displaystyle{ a^{(N-1)/r} \not \equiv 1 (mod N) }[/math] для некоторого целого [math]\displaystyle{ a }[/math], то [math]\displaystyle{ N }[/math] — простое.
Доказательство обобщенной теоремы можно найти в работе Sze[4].
История
Франсуа Прот (1852—1879) опубликовал теорему около 1878 года.
См. также
Примечания
- ↑ Public Key Cryptography:Applications and Attacks Архивная копия от 18 декабря 2013 на Wayback Machine (англ.)
- ↑ Deterministic Primality Proving on Proth Numbers Архивная копия от 7 мая 2021 на Wayback Machine (англ.)
- ↑ The Top Twenty Largest Known Primes Архивная копия от 16 июля 2012 на Wayback Machine (англ.)
- ↑ Sze, 2007.
Ссылки
- 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.