Ru.Wikipedia.Org - Теорема Прота

Меню
Главная
Случайная статья
Настройки

Теорема Прота
Материал из https://ru.wikipedia.org

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

Содержание

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

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

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

a^{(p-1)/2}\equiv -1{\pmod {p}}

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

(а) Пусть p — простое. Тогда для любого квадратичного невычета a:

a^{(p-1)/2}\equiv -1{\pmod {p}}

по критерию Эйлера.

(б) Пусть

a^{(p-1)/2}\equiv -1{\pmod {p}}

для некоторого квадратичного невычета a. Используем критерий Поклингтона, где

n=2^{k}+1

. Тогда

q=2

— единственный простой делитель

n-1

. Проверим выполнение условий критерия:

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

Так как условие

2^{k}>{\sqrt {n}}-1

выполнено, n — простое. ^[1]

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

Теорема Прота может быть использована для тестирования простоты чисел Прота. Алгоритм вероятностного теста, основанного на теореме, выглядит следующим образом: Случайным образом выбирается целое число

a

, такое что

a\not \equiv 1{\pmod {p}}\

и вычисляет

b\equiv a^{(p-1)/2}{\pmod {p}}\

. Возможны следующие исходы:

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

Исход (4) является причиной того, что тест вероятностный. В случае (1)

a

— квадратичный невычет по модулю

p

. Процедура повторяется пока простота

p

не будет установлена. Если

p

— простое, то тест с вероятностью

1/2

подтвердит это за одну итерацию, так как количество квадратичных невычетов по модулю

p

ровно

(p-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]

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

Лемма. Пусть

n=l^{k}

для некоторого простого l и

k\geqslant 1

. Пусть

r^{e}

— степень простого числа, где

r\neq l

. Если

r^{e}{\mathcal {j}}\phi (n)

r^{e}>{\sqrt {n}}

, то n — простое.

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

r^{e}

— делитель

\phi (n)=(l-1)l^{k-1}

, поэтому

r^{e}{\mathcal {j}}l-1

. Если

k>1

, то

\phi (n)\geqslant (l-1)l>r^{2}e>n

— противоречие. Следовательно

k=1

n

— простое.

Теорема (обобщенная теорема Прота). Пусть

N=r^{e}t+1

для некоторого простого

r

и целых

e,t\geqslant 1

. Пусть

r^{e}>t

. Если

a^{N-1}\equiv 1(modN)

a^{(N-1)/r}\not \equiv 1(modN)

для некоторого целого

a

, то

N

— простое.

Доказательство обобщенной теоремы можно найти в работе 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.