Miller-Rabin teszt

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. szeptember 24-én felülvizsgált verziótól ; az ellenőrzések 7 szerkesztést igényelnek .

A Miller-Rabin teszt egy valószínűségi polinomiális primalitásteszt . A Miller-Rabin teszt, valamint a Fermat teszt és a Solovay-Strassen teszt hatékonyan meghatározhatja, hogy egy adott szám összetett -e . Nem használható azonban annak szigorú bizonyítására , hogy egy szám prím . A Miller-Rabin tesztet azonban gyakran használják a kriptográfiában nagy véletlenszerű prímszámok generálására .

Történelem

A Miller-Rabin algoritmus a Gary Miller által 1976 -ban kifejlesztett Miller-algoritmus módosítása . Miller algoritmusa determinisztikus , de helyessége a nem bizonyított kiterjesztett Riemann-hipotézisen alapul [1] . Michael Rabin 1980 -ban módosította [2] . A Miller-Rabin algoritmus nem függ a hipotézis érvényességétől, hanem valószínűségi.

Alkalmazás

Mivel sok titkosítási algoritmus kriptográfiai erőssége titkos kulcsokon alapul, amelyek létrehozásához prímszámok szükségesek (például így működik az RSA -rejtjel ), az ilyen kulcsok létrehozásakor fontos, hogy gyorsan ellenőrizni lehessen a nagy számokat elsődlegessége. A valószínűségi primalitási tesztek, mint például a Miller-Rabin teszt és a Solovay-Strassen teszt a determinisztikus tesztekhez képest nagyobb hatékonyságot és könnyebb kifejezést mutatnak [3] . A Miller-Rabin algoritmus lehetővé teszi, hogy rövid időn belül ellenőrzést hajtson végre, és ugyanakkor meglehetősen kicsi a valószínűsége annak, hogy a szám valóban összetett. [négy]

Hogyan működik az algoritmus

A Fermat és Nightingale-Strassen tesztekhez hasonlóan a Miller-Rabin teszt is a prímszámokra érvényes egyenlőségsorozat ellenőrzésére támaszkodik. Ha legalább egy ilyen egyenlőség meghiúsul, az bizonyítja, hogy a szám összetett [5] .

A Miller-Rabin teszthez a következő állítást használjuk:

Legyen egy prímszám és , ahol páratlan. Ekkor az alábbi feltételek közül legalább egy teljesül: $n$ $n-1=2^{s}d$ $d$ $a$ $\mathbb {Z} _{n}$

$a^{d}\equiv 1{\pmod {n))$
Van egy ilyen egész szám $r<s$ $a^{2^{r}d}\equiv -1{\pmod {n))$

Bizonyíték Lemma az egység négyzetgyökeiről egy véges mezőben :

\mathbb {Z} _{p}

A végső mezőben (prím esetén) nincs egység négyzetgyöke, kivéve az 1 , -1 számokat $\mathbb {Z} _{p}$ $p$

Bizonyíték

Legyen:

{a} \equiv {\sqrt{1} }\pmod{p}

Akkor:

a^{2} \equiv 1\pmod{p}

a^{2} {-1}\equiv 0\pmod{p}

(a + 1)( a - 1) \equiv 0\pmod{p}

Euklidész lemmája szerint :

\bigg [ \begin{mátrix} {a - 1} \equiv {0}\pmod{p} \\ {a + 1} \equiv {0}\pmod{p} \end{mátrix}

\bigg [ \begin{mátrix} {a}\equiv {1}\pmod{p} \\ {a}\equiv {-1}\pmod{p} \end{mátrix}

Fermat kis tétele szerint :

a^{n-1}\equiv 1{\pmod {n)).

Kivonjuk a szám négyzetgyökét . A fent bizonyított lemma szerint minden lépésnél 1 -es vagy -1 modulo számot kapunk . Ha valamelyik lépésnél -1 -et kapunk , akkor az egyenlőségek közül a második teljesül. Ellenkező esetben az utolsó lépésben (mert ), azaz az első egyenlőség teljesül. $a^{n-1}$ $n$ ${\sqrt[{{2}^{s}}]{a^{n-1}}}=a^{d}$ $n-1=2^{s}d$

Ha ez az állítás (1. vagy 2. feltétel) bizonyos számokra és (nem feltétlenül prímre) teljesül , akkor a számot Miller prímtanújának , magát a számot pedig valószínűségi prímnek nevezzük . (Véletlenszerűen 25% esély van arra, hogy egy összetett számot összetévesztünk prímszámmal, de ez csökkenthető, ha másokat keres .) $a$ $n$ $a$ $n$ $n$ $a$ $a$

Abban az esetben, ha a bizonyított állítás ellentmondása teljesül, vagyis ha van olyan szám , amely: $a$

a^{d} \not\equiv 1\pmod{n}

és

\forall r:\ 0\le r\le s-1:\ a^{2^rd} \not\equiv -1\pmod{n},

akkor a szám nem prímszám. Ebben az esetben a számot annak tanújának nevezzük, hogy a szám összetett. $n$ $a$ $n$

Páratlan összetett számok esetén Rabin tétele szerint nincs több tanúja az egyszerűségnek, hol van az Euler-függvény , így annak a valószínűsége, hogy egy véletlenszerűen kiválasztott szám az egyszerűség tanúja lesz, kisebb, mint 1/4 [2] [6] . $n$ $\varphi (n)/4$ $\varphi (n)$ $a$

A teszt célja, hogy ellenőrizze a véletlenszerűen kiválasztott számokat , vajon tanúi-e a szám elsődlegességének . Ha bizonyíték van arra, hogy a szám összetett, akkor a szám valóban összetett. Ha a számokat ellenőriztük , és mindegyik prímnek bizonyult, akkor a szám prímnek minősül. Egy ilyen algoritmus esetén kisebb lesz annak a valószínűsége, hogy egy prímszámra összetett számot veszünk [7] . $a<n$ $n$ $k$ $(1/4)^{k}$

Nagy számok ellenőrzéséhez véletlenszerű számokat szokás választani , mivel az 1, 2, ..., n − 1 számok között nem ismert az elsődlegesség és az összetett szám tanúinak megoszlása. Arnolt [8] konkrétan egy 397 bites összetett számot ad meg, amelyre minden 307-nél kisebb szám az egyszerűség bizonyítéka. $a$

Példa

Tegyük fel, hogy meg akarjuk határozni, hogy n = 221 prím-e. Írjuk fel n − 1 = 220 -at 2 2 55-nek, tehát s = 2 és d = 55. Tetszőlegesen kiválasztunk egy olyan a számot , amelyre 0 < a < n , mondjuk a = 174. Folytassa a számításokkal:

a 2 0 d mod n = 174 55 mod 221 = 47 ≠ 1, n - 1
a 2 1 d mod n = 174 110 mod 221 = 220 = n − 1.

Mivel 220 ≡ −1 mod n , 221 vagy prím, vagy 174 hamis tanúja, hogy 221 prím. Vegyünk egy másik tetszőleges a -t , ezúttal a = 137-et választva:

a 2 0 d mod n = 137 55 mod 221 = 188 ≠ 1, n - 1
a 2 1 d mod n = 137 110 mod 221 = 205 ≠ n − 1.

Mivel a 137 annak tanúja, hogy a 221 összetett, a 174 valójában az egyszerűség hamis tanúja volt. Vegyük észre, hogy az algoritmus nem mond semmit a 221 tényezőiről (amelyek 13 és 17). Bizonyos esetekben azonban további számítások segítenek a számtényezők meghatározásában. [9]

Miller-Rabin algoritmus

Megvalósítás

A Miller-Rabin algoritmust az r körök számával paraméterezzük . Javasoljuk, hogy r nagyságrendű legyen , ahol n a vizsgálandó szám. $\log_2(n)$

Adott n esetén van egy s egész és egy páratlan t egész szám , hogy . Egy a véletlenszámot választunk , 1 < a < n . Ha a nem mutatja az n szám elsődlegességét, akkor az "n összetett" választ kapjuk , és az algoritmus véget ér. Ellenkező esetben a rendszer egy új véletlenszámot a kiválaszt , és az ellenőrzési eljárás megismétlődik. Miután r bizonyítékot találtunk az egyszerűségre, az "n valószínűleg prím" választ adjuk , és az algoritmus befejeződik [5] . $n-1 = 2^st$

Az algoritmus a következőképpen írható pszeudokódban :

Bemenet : n > 2, egy páratlan természetes szám, amelyet az elsődlegesség szempontjából ellenőrizni kell; k a körök száma. Kimenet : összetett , azt jelenti, hogy n egy összetett szám; valószínűleg prím azt jelenti, hogy n nagy valószínűséggel prím. Az n − 1 ábrázolása 2 s · t -ként , ahol t páratlan, megtehető úgy, hogy n - 1- et elosztjuk 2-vel. A hurok : ismételje meg k - szer: Válasszon egy véletlenszerű egész számot a [2, n − 2] x ← a t mod n intervallumban, a modulo hatványozási algoritmussal kiszámítva, ha x = 1 vagy x = n − 1, majd menjen az A hurok következő iterációjához . : ismételje meg az s − 1-szer x ← x 2 mod n ha x = 1, majd adja vissza az vegyületet , ha x = n − 1, majd lépjen az A ciklus következő iterációjához .

Rabin tételéből következik, hogy ha k véletlenszerűen kiválasztott szám tanúja lenne az n szám prímságának , akkor annak a valószínűsége, hogy n összetett, nem haladja meg a -t . $4^{-k}$

Ezenkívül n nagy értékei esetén annak a valószínűsége, hogy egy összetett szám valószínűleg prímként deklaráljon, lényegesen kisebb, mint 4 − k . Damgard, Landrock és Pomerands [10] kiszámított néhány pontos hibahatárt, és egy módszert javasolt k értékének kiválasztására a kívánt hibahatár eléréséhez. Ilyen korlátok használhatók például valószínű prímszámok generálására. Mindazonáltal nem használhatók ismeretlen eredetű prímszámok tesztelésére, mivel a kriptográfiai rendszerekben a cracker megpróbálhat helyettesíteni egy pszeudoprímet, amikor prímszámra van szükség. Ilyen esetekben csak a 4 − k hibára hagyatkozhatunk .

Munka nehézségei

Feltételezve, hogy a szorzási idő logaritmikus, gyors modulo szorzást használva az algoritmus bonyolultsága , ahol a körök száma. Így az algoritmus futási ideje polinomiális. $O(k\log^3n)$ $k$

Az FFT használatával azonban lehetséges az algoritmus futási idejét -ra csökkenteni . Ebben az esetben, ha vesszük , ahol n az ellenőrizendő szám, akkor az algoritmus összetettsége egyenlő -val . [tizenegy] $O(k\log ^{2}(n)\log(\log(n))\log(\log(\log(n))))={\widetilde {O))(k\log ^{2}(n))$ $k = \log_2(n)$ ${\widetilde {O}}(\log ^{3}n)$

Erősen pszeudoprímek

Ha az a szám az n összetett páratlan szám egyszerűségének tanúja Miller szerint, akkor az n számot viszont erősen pszeudo -prímnek mondjuk az a bázisban . Ha egy n szám erősen pszeudoprím az a bázisban , akkor Fermat pszeudoprím az a bázisban és Euler-Jacobi pszeudoprím az a bázisban is . [3]

Például az erősen pszeudoprímek a 2. bázisban alkotják a következő sorozatot:

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, … ( OEIS sorozat A001262 )

a 3. bázisban pedig a következő sorrend:

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, … ( OEIS sorozat A020229 )

Jegyzetek

↑ Miller, 1975 .
↑ 12 Rabin , 1980 .
↑ 1 2 Menezes, Oorschot, Vanstone, 1996 , pp. 141.
↑ Kormen, 2015 , p. 147.
↑ 1 2 Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algoritmusok: konstrukció és elemzés. - 3. - Moszkva: Williams, 2013. - S. 1012-1015. — 1328 p. - ISBN 978-5-8459-1794-2 .
↑ Schoof, 2008 .
↑ Monier, 1980 .
↑ Arnault, 1995 .
↑ Baillie, Wagstaff, 1980 .
↑ Damgård, Landrock, Pomerance, 1993 .
↑ Bruce Schneier. Alkalmazott kriptográfia. - Moszkva: Triumph, 2013. - S. 298. - 816 p.

Irodalom

Miller G. Riemann hipotézise és tesztjei az elsődlegességre // STOC '75 :of hetedik éves ACM szimpózium a számítástechnikai elméletről - New York, NY, USA : ACM , 1975. - P. 234-239. doi : 10.1145/800116.803773
Rabin M. O. Valószínűségi algoritmus a primalitás tesztelésére // J. Számelmélet. / D. Goss - Elsevier BV , 1980. - Vol. 12, Iss. 1. - P. 128-138. — ISSN 0022-314X ; 1096-1658 - doi:10.1016/0022-314X(80)90084-0
Baillie R. , Samuel S. Wagstaff, Jr. Lucas Pseudoprimes (angol) // Math. Összeg. - AMS , 1980. - 1. évf. 35, Iss. 152. - P. 1391-1417. — ISSN 0025-5718 ; 1088-6842 - doi:10.1090/S0025-5718-1980-0583518-6
Monier L. Két hatékony valószínűségi elsődlegességi vizsgálati algoritmus értékelése és összehasonlítása (angol) // Theoretical Computer Science - Elsevier BV , 1980. - 20. évf. 12, Iss. 1. - P. 97-108. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/0304-3975(80)90007-9
Damgård I. , Landrock P. , Pomerance C. Average Case Error Estimates for the Strong Probable Prime Test // Math . Összeg. - AMS , 1993. - Vol. 61, Iss. 203. - P. 177-194. — ISSN 0025-5718 ; 1088-6842 - doi:10.2307/2152945
Arnault F. Carmichael-számok, amelyek erős pszeudoprímek több bázishoz // Journal of Symbolic Computation - Elsevier BV , 1995. - Vol. 20, Iss. 2. - P. 151-161. — ISSN 0747-7171 ; 1095-855X - doi:10.1006/JSCO.1995.1042
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (angol) - CRC Press , 1996. - 816 p. — ( Diszkrét matematika és alkalmazásai ) — ISBN 978-0-8493-8523-0
Schoof R. Four Primality Testing Algorithms (angol) // Algorithmic Number Theory : Lattices, Number Fields, Curves and Cryptography / J. P. Buhler , P. Stevenhagen - Cambridge : Cambridge University Press , 2008. - P. 69-81. - ( Matematikai Tudományok Kutatóintézetének kiadványai ; 44. köt.) - ISBN 978-0-521-80854-5
Kormen T. H. Algoritmusok : Bevezető tanfolyam / ford. I. Krasikov - M. : Williams , 2015. - 208 p. — ISBN 978-5-8459-1868-0 , 978-5-8459-2073-7

Linkek

Yu. V. Neszterenko. fejezet 4.4. Hogyan lehet megkülönböztetni egy összetett számot az egyszerűtől // Bevezetés a kriptográfiába / Szerk. V. V. Jascsenko. - Péter, 2001. - 288 p. - ISBN 5-318-00443-1 . Archivált : 2008. február 25. a Wayback Machine -nél
Példák az algoritmus megvalósítására számos programozási nyelven
S. B. Gashkov. A valószínűségi Miller-Rabin teszt egyszerűsített indoklása a számok elsődlegességének tesztelésére .
Weisstein, Eric W. Rabin-Miller Strong Pseudoprime Test (angol nyelven) a Wolfram MathWorld weboldalán .
"SPRP rekordok"
Crandall, R. és Pomerance, C. Valószínű prímszámok és tanúk // Prímszámok. - Springer-Verlag, 2001. - ISBN 978-0387252827 .

Szótárak és enciklopédiák	Britannica (online)

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus