Pocklingtonovo kritérium

Pocklingtonův test je deterministický test primality vyvinutý Henrym Pocklingtonem a Derrickem Henry Lehmerem . Pocklingtonův test vám umožňuje určit, zda je dané číslo prvočíslo .

Pocklingtonova věta

Nechť kde q je prvočíslo, . Pokud existuje celé číslo takové, že gcd , pak každý prvočíselný dělitel čísla má tvar pro nějaké přirozené . $n=q^{k}R+1$ $k\geqslant 1$ $A$ $a^{n-1} \equiv 1 \pmod n$ $(a^{{(n-1)}/q}-1,n)=1$ $p$ $n$ $p=q^{k}r+1$ $r$

Důkaz

Dovolit být hlavním dělitelem . Pak z podmínek věty vyplývá, že a . Dostaneme tedy, že modulo řád prvku splňuje podmínky: , kde je nějaké celé číslo. Řekněme, že rozděluje . V tomto případě kde je celé číslo. Proto je to nemožné. Protože , potom je dělitelné . Číslo se však musí dělit Proto pro některé . Věta byla prokázána. $p$ $n$ $a^{n-1}=1{\pmod {p}}$ $a^{(n-1)/q}\neq 1{\pmod {p}}$ $m$ $A$ $p$ $n-1=md$ $d$ $q$ $d$ $(n-1)/q=m(d/q)$ $(d/q)$ $a^{(n-1)/q}=1{\pmod {p))$ $n-1=md=q^{k}R$ $m$ $q^k$ $m$ $p-1$ $p=q^{k}r+1$ $r$

The Pocklington Criterion

Nechť je přirozené číslo. Nechť má číslo prvočíselného dělitele a . Pokud existuje celé číslo takové, že jsou splněny následující dvě podmínky: $n$ $n-1$ $q$ $q>{\sqrt {n}}-1$ $A$

$a^{n-1} \equiv 1 \pmod n$
čísla a coprime, $n$ $a^{(n-1)/q}-1$

pak je prvočíslo. $n$

Důkaz

Předpokládejme, že se jedná o složené číslo. Pak je tu prvočíslo — dělitel , a . Všimněte si, že , tedy a jsou coprime. Proto existuje nějaké celé číslo takové, že . Ale v tomto případě (vzhledem k podmínce 1)). Ale tímto způsobem je získán rozpor s podmínkou 2). Proto je prvočíslo. $n$ $p$ $n$ $p<{\sqrt {n))$ $q>p-1$ $q$ $p-1$ $u$ $uq\equiv 1{\pmod {p-1}}$ $a^{(n-1)/q}\equiv a^{uq(n-1)/q}=a^{u(n-1)}\equiv 1{\pmod {p))$ $n$

Rozsah

Na rozdíl od Salridgeova teorému nevyžaduje Pocklingtonovo kritérium znalost úplného rozkladu čísla na prvočísla a umožňuje omezit se na částečnou rozklad čísla . Je vhodný pro testování na prvočíslo za předpokladu, že je dělitelný prvočíslem a také pokud jej lze najít a dokázat jako prvočíslo. $n-1$ $n-1$ $n-1$ $q>{\sqrt {n}}-1$ $q$

Za zmínku také stojí, že toto kritérium je pravděpodobnostní pouze v tom smyslu, že náhodně vybrané číslo buď může splnit podmínku GCD , nebo ne. Jestliže je liché prvočíslo, , gcd , pak pro náhodně zvolené číslo je tato pravděpodobnost . Jakmile je však takový nalezen , kritérium prokáže, že jde o prvočíslo. Na rozdíl od pravděpodobnostních testů (jako je např. Miller-Rabinův test, Solovay-Strassenův test atd.) je závěr Pocklingtonova testu zcela jednoznačný. $A$ $(a^{(n-1)/q}-1,n)=1$ $n=RF+1$ $F>{\sqrt {n}}-1$ $F=q_{1}^{\alpha _{1}}q_{2}^{\alpha _{2}}...q_{k}^{\alpha _{k)),$ $(R,F)=1$ $1<a<n$ $\prod _{i=1}^{k}(1-{\frac {1}{q_{i))})$ $A$ $n$

Největším problémem spojeným s použitím tohoto kritéria může být potřeba najít prvočíselného dělitele čísla , který lze v praxi redukovat na plnou faktorizaci. Najít toho pravého je menší problém. Podle Neila Koblitz je hodnota často vhodná pro testování pomocí Pocklingtonova testu. $n-1$ $A$ $a=2$

Odhad výpočetní složitosti

Přestože Pocklingtonův test dokazuje, že číslo je prvočíslo pouze při správné volbě , je možné odhadnout jeho algoritmickou složitost za předpokladu, že jsme jej zvolili správně. Výpočetní složitost testu bude součtem složitosti faktorizace čísla a čísla . Při použití faktorizačních algoritmů se subexponenciální složitostí může být shora omezena hodnotou uvedenou v L-notaci , kde a závisí na volbě faktorizačního algoritmu. $n$ $A$ $n$ $a^{(n-1)/q}-1$ $L_{a^{n}}[\alpha ,c]$ $\alpha$ $C$

Příklad

Dokažme, že číslo je prvočíslo. Najdeme jednoduchý dělitel čísla , tedy 30. Je , a . Číslo a=2 splňuje obě kritéria: $n=31$ $n-1$ $q=5$ $5>{\sqrt {31}}-1$

$2^{30}\equiv 1{\pmod {31}}$
čísla a coprime, $31$ $2^{(31-1)/5}-1$

Proto je číslo 31 prvočíslo podle Pocklingtonova kritéria

Speciální případy

Speciálním případem Pocklingtonova kritéria je Prothova věta , což je test prvočíselnosti pro Prothova čísla , kde je liché a . Vypadá to takto: $n=2^{k}R+1$ $R$ ${\displaystyle R<2^{k))$

Nechat , kde , , a ne dělit . Pak je prvočíslo právě tehdy, když je splněna podmínka . $n=2^{k}R+1$ ${\displaystyle R<2^{k))$ $Z<2^{k}+1$ $Z$ $R$ $n$ $Z^{(n-1)/2}=-1{\pmod {n))$

Viz také

Literatura

N. Koblitz, Kurz teorie čísel a kryptografie ISBN 5-94057-103-4
Yu. V. Romanets, PA Timofeev, VF Shangin, Informační bezpečnost v počítačových systémech a sítích. 2. vydání, ISBN 5-256-01518-4
A. V. Cheremushkin, Přednášky o aritmetických algoritmech v kryptografii ISBN 5-94057-060-7