Русская Википедия:Теорема Прота
В теории чисел теорема Прота является тестом простоты для чисел Прота.
Формулировка
Теорема Прота гласит: Шаблон:Рамка Если p — это число Прота вида <math>k\cdot 2^n + 1</math>, где k — нечётно и <math>k < 2^n </math>, то p — простое (называемое простым Прота) тогда и только тогда, когда для некоторого квадратичного невычета a выполняется сравнение:
- <math>a^{(p-1)/2}\equiv -1 \pmod{p}</math>
Доказательство
(а) Пусть p — простое. Тогда для любого квадратичного невычета a: <math>a^{(p-1)/2}\equiv -1 \pmod{p}</math> по критерию Эйлера.
(б) Пусть <math>a^{(p-1)/2}\equiv -1 \pmod{p}</math> для некоторого квадратичного невычета a. Используем критерий Поклингтона, где <math>n=2^k+1</math> . Тогда <math>q=2</math> — единственный простой делитель <math>n-1</math>. Проверим выполнение условий критерия:
- <math>a^{n-1} =(a^{(n-1)/2})^2 \equiv 1 \pmod n</math> — выполнено.
- числа n и <math>a^{(n-1)/q} -1 </math> взаимно просты — выполнено.
Так как условие <math>2^k > \sqrt {n} -1 </math> выполнено, n — простое. [1]
Тестирование чисел Прота на простоту
Теорема Прота может быть использована для тестирования простоты чисел Прота. Алгоритм вероятностного теста, основанного на теореме, выглядит следующим образом: Случайным образом выбирается целое число <math> a </math>, такое что <math> a \not \equiv 1 \pmod{p}\ </math> и вычисляет <math>b \equiv a^{(p-1)/2} \pmod{p}\ </math>. Возможны следующие исходы:
- <math> b \equiv -1 \pmod{p}\ </math>, тогда <math> p </math> — простое по теорема Прота.
- <math> b \not \equiv \pm 1 \pmod{p}\ </math> и <math>b^2 \equiv 1 \pmod{p}\ </math>, тогда <math> p </math> — составное, так как <math>gcd (b \pm 1, p) </math> — нетривиальные делители <math>p</math>.
- <math> b^2 \not \equiv 1 \pmod{p}\ </math>, тогда p — составное по малой теореме Ферма.
- <math> b \equiv 1 \pmod{p}\ </math>, тогда результат теста неизвестен.
Исход (4) является причиной того, что тест вероятностный. В случае (1) <math> a </math> — квадратичный невычет по модулю <math> p </math>. Процедура повторяется пока простота <math> p </math> не будет установлена. Если <math> p </math> — простое, то тест с вероятностью <math> 1/2 </math> подтвердит это за одну итерацию, так как количество квадратичных невычетов по модулю <math> p </math> ровно <math> (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.
Простые числа Прота
Простые числа Прота образуют последовательность:
На май 2017 года, крупнейшее известное простое Прота, 10223 · 231172165 + 1, найдено проектом Primegrid. Оно имеет 9383761 десятичных цифр и является крупнейшим известным простым, не являющимся простым Мерсенна.[3]
Обобщенная теорема Прота
Лемма. Пусть <math>n = l^k </math> для некоторого простого l и <math> k \geqslant 1 </math>. Пусть <math>r^e </math> — степень простого числа, где <math>r \ne l </math>. Если <math> r^e \mathcal {j} \phi(n) </math> и <math> r^e>\sqrt n </math>, то n — простое.
- Доказательство. <math>r^e </math> — делитель <math> \phi(n) = (l-1) l ^ {k-1} </math>, поэтому <math> r^e \mathcal {j} l -1 </math>. Если <math> k > 1 </math>, то <math> \phi(n) \geqslant (l-1)l > r^2e > n </math> — противоречие. Следовательно <math> k = 1 </math> и <math> n </math> — простое.
Теорема (обобщенная теорема Прота). Пусть <math> N=r^{e}t + 1 </math> для некоторого простого <math> r </math> и целых <math> e,t\geqslant 1 </math>. Пусть <math> r^e > t</math>. Если <math>a^{N-1} \equiv 1 (mod N) </math> и <math>a^{(N-1)/r} \not \equiv 1 (mod N) </math> для некоторого целого <math> a </math>, то <math>N</math> — простое.
Доказательство обобщенной теоремы можно найти в работе SzeШаблон:Sfn.
История
Шаблон:Нп1 (1852—1879) опубликовал теорему около 1878 года.
См. также
Примечания
Ссылки
- Шаблон:MathWorld
- «Обзор проверок на простоту», Кучин, 2005
- Шаблон:Книга
