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

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

Лема[ред. | ред. код]

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

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

тоді $n$ — просте.

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

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

Теорема Поклінґтона[ред. | ред. код]

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

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

Вислід[ред. | ред. код]

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

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

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

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

Кількість перевірок[ред. | ред. код]

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

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