Pocklington-kritérium

A Pocklington -teszt egy determinisztikus primalitásteszt , amelyet Henry Pocklington és Derrick Henry Lehmer fejlesztett ki . A Pocklington-teszt lehetővé teszi annak meghatározását, hogy egy adott szám prím -e .

Pocklington-tétel

Legyen ahol q egy prímszám, . Ha van olyan egész szám , hogy gcd , akkor a szám minden prímosztója valamilyen természetes alakkal rendelkezik . $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$

Bizonyítás

Legyen főosztója . Ekkor a tétel feltételeiből következik, hogy és . Ebből kapjuk, hogy az elem modulo sorrendje teljesíti a feltételeket: , ahol valamilyen egész szám. Tegyük fel, hogy oszt . Ebben az esetben ahol egy egész szám. Ezért ez lehetetlen. Mivel , akkor osztható -vel . A számnak azonban osztania kell Ezért néhány . A tétel bizonyítást nyert. $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$ ${\megjelenítési stílus (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$

A Pocklington-kritérium

Legyen természetes szám. Legyen a számnak prímosztója , és . Ha van olyan egész szám , amelyre a következő két feltétel teljesül: $n$ $n-1$ $q$ $q>{\sqrt {n}}-1$ $a$

$a^{n-1} \equiv 1 \pmod n$
számok és koprím, $n$ $a^{(n-1)/q}-1$

akkor egy prímszám. $n$

Bizonyítás

Tegyük fel, hogy ez egy összetett szám. Ezután van egy prímszám — osztó , és . Vegye figyelembe, hogy ezért a és a koprím. Ezért van néhány olyan egész szám , hogy . De ebben az esetben (az 1. feltétel miatt)). De így a 2) feltétel ellentmondása keletkezik. Ezért egy prímszám. $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$

Hatókör

Salridge tételével ellentétben a Pocklington-kritérium nem követeli meg egy szám prímtényezőkké való teljes faktorizálásának ismeretét, és lehetővé teszi, hogy egy szám részleges faktorizálására korlátozódjunk . Alkalmas a prímszám vizsgálatára, feltéve, hogy osztható egy prímszámmal , és akkor is, ha megtalálható és bebizonyítható, hogy prím. $n-1$ $n-1$ $n-1$ $q>{\sqrt {n}}-1$ $q$

Azt is érdemes megjegyezni, hogy ez a kritérium csak abban az értelemben valószínűségi, hogy egy véletlenszerűen kiválasztott szám vagy teljesíti a GCD feltételt , vagy nem. Ha egy páratlan prímszám, , gcd , akkor egy véletlenszerűen kiválasztott szám esetén ez a valószínűség . Azonban amint ezt megtaláljuk , a kritérium bebizonyítja, hogy prímszám. Ellentétben a valószínűségi tesztekkel (mint például a Miller-Rabin teszt, a Solovay-Strassen teszt stb.), a Pocklington-teszt következtetése meglehetősen határozott. $a$ ${\megjelenítési stílus (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)),$ ${\megjelenítési stílus (R,F)=1}$ $1<a<n$ $\prod _{i=1}^{k}(1-{\frac {1}{q_{i))})$ $a$ $n$

Ennek a kritériumnak a használatával kapcsolatos legnagyobb nehézséget az jelentheti, hogy meg kell találni a szám prímosztóját , amely a gyakorlatban a teljes faktorizálásra redukálható. A megfelelő megtalálása kevésbé jelent kihívást. Neil Koblitz szerint az érték gyakran alkalmas a Pocklington-teszttel való tesztelésre. $n-1$ $a$ $a=2$

A számítási komplexitás becslése

Bár a Pocklington-teszt csak a helyes megválasztásával bizonyítja, hogy egy szám prím, lehetséges az algoritmus bonyolultsága becslése abból a feltételezésből kiindulva, hogy helyesen választottuk ki. A teszt számítási összetettsége egy szám és egy szám faktorálásának összetettségének összege lesz . Szubexponenciális bonyolultságú faktorizációs algoritmusok használatakor felülről korlátozható az L-jelölésben megadott értékkel , ahol és a faktorizációs algoritmus megválasztásától függ. $n$ $a$ $n$ $a^{(n-1)/q}-1$ $L_{a^{n}}[\alpha ,c]$ $\alpha$ $c$

Példa

Bizonyítsuk be, hogy a szám prím. Keressük a szám egyszerű osztóját , azaz 30-at. Ez , és . Az a=2 szám mindkét kritériumot kielégíti: $n=31$ $n-1$ $q=5$ $5>{\sqrt {31}}-1$

$2^{30}\equiv 1{\pmod {31}}$
számok és koprím, $31$ $2^{(31-1)/5}-1$

Ezért a 31-es szám prímszám a Pocklington-kritérium szerint

Különleges esetek

A Pocklington-kritérium speciális esete a Proth-tétel , amely Proth-számok primalitástesztje , ahol páratlan és . Ez így néz ki: $n=2^{k}R+1$ $R$ ${\displaystyle R<2^{k))$

Legyen , ahol , , és ne osszuk . Akkor egy prímszám akkor és csak akkor, ha a feltétel teljesül . $n=2^{k}R+1$ ${\displaystyle R<2^{k))$ $Z<2^{k}+1$ $Z$ $R$ $n$ $Z^{(n-1)/2}=-1{\pmod {n))$

Lásd még

Irodalom

N. Koblitz, Számelmélet és kriptográfiai tanfolyam ISBN 5-94057-103-4
Yu. V. Romanets, PA Timofejev, VF Shangin, Információbiztonság számítógépes rendszerekben és hálózatokban. 2. kiadás, ISBN 5-256-01518-4
A. V. Cheremushkin, Előadások az aritmetikai algoritmusokról a kriptográfiában ISBN 5-94057-060-7