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

Нехай ${\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=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}$ імовірно складене і це можна перевірити через застосування ймовірнісного тесту на простоту.

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