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

Тест на простоту Поклінґтона (Шаблон:Lang-en) — тест на простоту розроблений Генрі Кабурн Поклінґтоном і Деріком Генрі Лемером для визначення чи є число $n$ простим. На виході тесту або доведення простоти, або неможливість доведення.

Лема

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

1. $a^{n-1}\equiv 1(\mathrm{mod}n),$
2. $a^{(n-1)/q}\equiv ̸1(\mathrm{mod}n);$

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

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

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

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

Теорема Поклінґтона (Шаблон:Lang-en) (1914): Нехай $n-1=q^{k}R,$ де $q$ — просте, яке не ділить $R.$ Якщо існує ціле таке, що $a^{n-1}\equiv 1(\mathrm{mod}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,$ що задовольняє:

1. $a^{n-1}\equiv 1(\mathrm{mod}n);$
2. $\gcd (a^{(n-1)/q_j}-1,n)=1$ для кожного $j,1\le j\le 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\le a\le n-1,$ задовольняє обом умовам: $a^{n-1}\equiv (\mathrm{mod}n);$ і $\gcd (a^{(n-1)/q_j}-1,n)=1$ для кожного $j,$ $1\le j\le t,$ становить $\prod _{j=1}^t(1-1/q_j)\ge 1-\sum _{j=1}^{t}1/q_j.$

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

Джерела

• Finding primes & proving primality Шаблон:Ref-en
• Шаблон:Cite book