Тест на простоту Поклінґтона

Тест на простоту Поклінґтона (англ. Pocklington–Lehmer primality test) — тест на простоту розроблений Генрі Кабурн Поклінґтоном і Деріком Генрі Лемером для визначення чи є число ${\displaystyle n}$ простим. На виході тесту або доведення простоти, або неможливість доведення.

Лема

Нехай ${\displaystyle n>1.}$ Якщо для кожного простого дільника ${\displaystyle q}$ для ${\displaystyle n-1}$ існує ціле таке, що

1. ${\displaystyle a^{n-1}\equiv 1{\pmod {n}},}$
2. ${\displaystyle a^{(n-1)/q}\not \equiv 1{\pmod {n}};}$

тоді ${\displaystyle n}$ — просте.

Позначення: ${\displaystyle a|b}$ означає, що ${\displaystyle a}$ ділить ${\displaystyle b.}$

Доведення: Для того, щоб показати, що ${\displaystyle n}$ просте нам потрібно лише показати, що ${\displaystyle \phi (n)=n-1,}$ або простіше, що ${\displaystyle (n-1)|\phi (n).}$ Припустимо це не так, тоді існує просте ${\displaystyle q}$ і показник ${\displaystyle r>0}$ такий, що ${\displaystyle q^{r}|(n-1),}$ але не ділить ${\displaystyle \phi (n).}$ Для цього цілого ${\displaystyle q}$ ми маємо мати ціле, що задовольняє попереднім умовам. Тепер нехай ${\displaystyle m}$ буде порядком ${\displaystyle a}$ за модулем ${\displaystyle n,}$ тоді ${\displaystyle m|(n-1)}$ (перша умова), але не ділить ${\displaystyle (n-1)/q}$ (друга умова). Отже ${\displaystyle q^{r}}$ ділить ${\displaystyle m,}$ яке ділить ${\displaystyle \phi (n)}$ — протиріччя, яке доводить лему.

Теорема Поклінґтона

Теорема Поклінґтона (англ. Pocklington's Theorem) (1914): Нехай ${\displaystyle n-1=q^{k}R,}$ де ${\displaystyle q}$ — просте, яке не ділить ${\displaystyle R.}$ Якщо існує ціле таке, що ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$ і ${\displaystyle \gcd(a^{(n-1)/q}-1,n)=1,}$ тоді кожен простий дільник ${\displaystyle p}$ для ${\displaystyle n}$ має вигляд ${\displaystyle q^{k}r+1.}$

Доведення: Нехай ${\displaystyle p}$ — довільний простий дільник ${\displaystyle n,}$ і нехай ${\displaystyle m}$ буде порядком ${\displaystyle a}$ за модулем ${\displaystyle p.}$ Як і в лемі, ${\displaystyle m|(n-1)=q^{k}R}$ (перша умова для ${\displaystyle a),}$ але не ділить ${\displaystyle (n-1)/q=q^{k-1}R}$ (друга умова); отже ${\displaystyle q^{k}|m.}$ Звісно, ${\displaystyle m|(p-1)}$ і звідси висновок.

Вислід

Вислідом застосування теореми Поклінґтона до кожного простого степеневого дільника ${\displaystyle n}$ (плюс трошки роботи) є:

Теорема: Припустимо, що ${\displaystyle n-1=F\times R}$ (тобто ${\displaystyle F|(n-1)}$ ), де ${\displaystyle F>R,}$ ${\displaystyle \gcd(F,R)=1}$ і відома факторизація ${\displaystyle F=\prod _{j=1}^{t}q_{j}^{e_{j}}}$. Якщо існує ціле ${\displaystyle a,}$ що задовольняє:

1. ${\displaystyle a^{n-1}\equiv 1{\pmod {n}};}$
2. ${\displaystyle \gcd(a^{(n-1)/q_{j}}-1,n)=1}$ для кожного ${\displaystyle j,1\leq j\leq t,}$

тоді кожен простий дільник ${\displaystyle p}$ для ${\displaystyle n}$ конгруентний ${\displaystyle 1}$ за модулем ${\displaystyle F.}$ З цього випливає, що якщо ${\displaystyle F>{\sqrt {n}}-1,}$ тоді ${\displaystyle n}$ є простим.

Кількість перевірок

Нехай ${\displaystyle n=RF+1}$ буде непарним простим з ${\displaystyle F>{\sqrt {n}}-1}$ і ${\displaystyle \gcd(R,F)=1.}$ І нехай різними простими дільниками для ${\displaystyle F}$ будуть ${\displaystyle q_{1},q_{2},\dots ,q_{t}.}$ Тоді ймовірність, що випадково обрана база ${\displaystyle a,}$ ${\displaystyle 1\leq a\leq n-1,}$ задовольняє обом умовам: ${\displaystyle a^{n-1}\equiv {\pmod {n}};}$ і ${\displaystyle \gcd(a^{(n-1)/q_{j}}-1,n)=1}$ для кожного ${\displaystyle j,}$ ${\displaystyle 1\leq j\leq t,}$ становить ${\displaystyle \prod _{j=1}^{t}(1-1/q_{j})\geq 1-\sum _{j=1}^{t}1/q_{j}.}$

Отже, якщо відома факторизація дільника ${\displaystyle F>{\sqrt {n}}-1,}$ тоді для перевірки на простоту, можна просто обирати випадкові цілі в інтервалі ${\displaystyle [2,n-2]}$ доки на знайдеться таке, що задовольняє умовам 1 і 2, тобто ${\displaystyle n}$ просте. Якщо таке ${\displaystyle a}$ не знайшли після розумної кількості ітерацій,^[1] тоді ${\displaystyle n}$ імовірно складене і це можна перевірити через застосування ймовірнісного тесту на простоту.

Примітки

1. За кількість ітерацій можна взяти ${\displaystyle T,}$ де ${\displaystyle P^{T}\leq \left({\frac {1}{2}}\right)^{100},}$ і де ${\displaystyle P=1-\prod _{j=1}^{t}(1-1/q_{j}).}$

Джерела

• Finding primes & proving primality (англ.)
• Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (1997). Prime Number Issues (PDF). Handbook of Applied Cryptography. CRC Press. с. 143–144. ISBN 0-8493-8523-7.