Miller-Rabinův test

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. září 2020; kontroly vyžadují 7 úprav .

Miller-Rabinův test je test pravděpodobnostní polynomiální primality . Miller-Rabinův test spolu s Fermatovým testem a Solovay-Strassenovým testem mohou účinně určit, zda je dané číslo složené . Nelze jej však použít k přísnému dokazování , že číslo je prvočíslo . Miller-Rabinův test se však často používá v kryptografii ke generování velkých náhodných prvočísel .

Historie

Algoritmus Miller-Rabin je modifikací algoritmu Miller vyvinutého Garym Millerem v roce 1976 . Millerův algoritmus je deterministický , ale jeho správnost se opírá o neprokázanou rozšířenou Riemannovu hypotézu [1] . Michael Rabin jej upravil v roce 1980 [2] . Miller-Rabinův algoritmus nezávisí na platnosti hypotézy, ale je pravděpodobnostní.

Aplikace

Vzhledem k tomu, že kryptografická síla mnoha šifrovacích algoritmů je založena na tajných klíčích, jejichž vytvoření vyžaduje prvočísla (například takto funguje šifra RSA ), je při vytváření takových klíčů důležité mít možnost rychle zkontrolovat, zda velká čísla primálnost. Pravděpodobnostní testy primality, jako je Miller-Rabinův test a Solovay-Strassenův test , vykazují větší efektivitu použití a snadnost vyjádření ve srovnání s deterministickými testy [3] . Algoritmus Miller-Rabin vám umožňuje provést kontrolu v krátkém čase a zároveň poskytnout poměrně malou pravděpodobnost, že číslo je skutečně složené. [čtyři]

Jak algoritmus funguje

Stejně jako testy Fermat a Nightingale-Strassen se i test Miller-Rabin spoléhá na kontrolu řady rovností, které platí pro prvočísla. Pokud alespoň jedna taková rovnost selže, dokazuje to, že číslo je složené [5] .

Pro Miller-Rabinův test se používá následující tvrzení:

Nechť je prvočíslo a , kde je liché. Pak je splněna jakákoli z alespoň jedné z následujících podmínek: $n$ $n-1=2^{s}d$ $d$ $A$ $\mathbb {Z} _{n}$

$a^{d}\equiv 1{\pmod {n))$
Existuje celé číslo takové, že $r<s$ $a^{2^{r}d}\equiv -1{\pmod {n))$

Důkaz Lemma o odmocninách jednoty v konečném poli :

\mathbb {Z} _{p}

V koncovém poli (pro prvočíslo ) nejsou žádné odmocniny jednoty, kromě čísel 1 , -1 $\mathbb {Z} _{p}$ $p$

Důkaz

Nechat:

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

Pak:

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

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

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

Podle Euklidova lemmatu :

\bigg [ \begin{matrix} {a - 1} \equiv {0}\pmod{p} \\ {a + 1} \equiv {0}\pmod{p} \end{matrix}

\bigg [ \begin{matrix} {a}\equiv {1}\pmod{p} \\ {a}\equiv {-1}\pmod{p} \end{matrix}

Podle Fermatovy malé věty :

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

Vytáhneme druhé odmocniny čísla . Podle výše dokázaného lemmatu dostaneme v každém kroku číslo 1 nebo -1 modulo . Pokud v některém kroku dostaneme -1 , pak je splněna druhá z rovností. V opačném případě bude v posledním kroku (protože ), tj. bude splněna první rovnost. $a^{n-1}$ $n$ ${\sqrt[{{2}^{s}}]{a^{n-1}}}=a^{d}$ $n-1=2^{s}d$

Pokud je toto tvrzení (podmínka 1 nebo 2) pro některá čísla splněno a (ne nutně prvočíslo), pak se toto číslo nazývá Millerův prvočíslo a samotné číslo se nazývá pravděpodobné prvočíslo . (Náhodně existuje 25% pravděpodobnost, že složené číslo zaměníte za prvočíslo, ale lze to snížit kontrolou na jiné .) $A$ $n$ $A$ $n$ $n$ $A$ $A$

V případě , že je splněn protiklad prokázaného tvrzení, to znamená, pokud existuje takový počet , že: $A$

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

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

pak číslo není prvočíslo. V tomto případě se číslo nazývá svědkem, že číslo je složené. $n$ $A$ $n$

Pro lichá složená čísla podle Rabinovy věty již neexistují svědci jednoduchosti, kde je Eulerova funkce , takže pravděpodobnost, že náhodně vybrané číslo bude svědkem jednoduchosti, je menší než 1/4 [2] [6] . $n$ $\varphi (n)/4$ $\varphi (n)$ $A$

Myšlenkou testu je zkontrolovat náhodně vybraná čísla , zda jsou svědky prvotřídnosti čísla . Pokud existuje důkaz, že číslo je složené, pak je číslo skutečně složené. Pokud byla čísla zkontrolována a všechna se ukázala jako prvočísla, pak je číslo považováno za prvočíslo. Pro takový algoritmus bude pravděpodobnost přijetí složeného čísla pro prvočíslo menší [7] . $a<n$ $n$ $k$ $(1/4)^{k}$

Pro kontrolu velkých čísel je zvykem volit náhodná čísla, protože rozdělení svědků primality a svědků složeného čísla mezi čísly 1, 2, ..., n − 1 není předem známo. Zejména Arnolt [8] uvádí 397bitové složené číslo, pro které jsou všechna čísla menší než 307 důkazem jednoduchosti. $A$

Příklad

Předpokládejme, že chceme určit, zda n = 221 je prvočíslo. Zapišme n − 1 = 220 jako 2 2 55, tedy s = 2 a d = 55. Libovolně zvolíme číslo a takové, že 0 < a < n , řekněme a = 174. Přejdeme k výpočtům:

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.

Protože 220 ≡ −1 mod n , 221 je buď prvočíslo, nebo 174 je falešný svědek toho, že prvočíslo je 221. Vezměte další libovolné a , tentokrát zvolte a = 137:

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.

Protože 137 je svědkem toho, že 221 je složené, číslo 174 bylo ve skutečnosti falešným svědkem jednoduchosti. Všimněte si, že algoritmus nám neříká nic o faktorech 221 (což jsou 13 a 17). V některých případech však dodatečné výpočty pomáhají získat faktory čísla. [9]

Miller-Rabinův algoritmus

Implementace

Miller-Rabinův algoritmus je parametrizován počtem kol r . Doporučuje se vzít r řádově , kde n je číslo, které se má zkontrolovat. $\log_2(n)$

Pro dané n existuje celé číslo s a liché celé číslo t takové, že . Je vybráno náhodné číslo a , 1 < a < n . Jestliže a není svědkem prvočísla čísla n , pak je dána odpověď "n je složená" a algoritmus končí. Jinak se vybere nové náhodné číslo a a postup ověření se zopakuje. Po nalezení r důkazu jednoduchosti je dána odpověď "n je pravděpodobně prvočíslo" a algoritmus končí [5] . $n-1 = 2^st$

Algoritmus lze napsat v pseudokódu takto:

Vstup : n > 2, liché přirozené číslo, které má být testováno na primálnost; k je počet kol. Výstup : kompozitní , znamená, že n je složené číslo; pravděpodobně prvočíslo znamená, že n je s vysokou pravděpodobností prvočíslo. Znázornění n − 1 jako 2 s · t , kde t je liché, lze provést postupným dělením n - 1 2. smyčka A: opakujte k krát: Vyberte náhodné celé číslo a v intervalu [2, n − 2] x ← a t mod n , vypočítané pomocí umocňovacího algoritmu modulo , pokud x = 1 nebo x = n − 1, pak přejděte k další iteraci smyčky A smyčky B : opakujte s − 1 krát x ← x 2 mod n , pokud x = 1, pak vraťte složenou , pokud x = n − 1, pak přejděte k další iteraci cyklu A vraťte složený návrat pravděpodobně prvočíslo

Z Rabinovy věty vyplývá, že pokud k náhodně vybraných čísel bylo svědkem prvotřídnosti čísla n , pak pravděpodobnost, že n je složené, nepřesahuje . $4^{-k}$

Také pro velké hodnoty n je pravděpodobnost deklarování složeného čísla pravděpodobně prvočíslo podstatně menší než 4 − k . Damgard, Landrock a Pomerands [10] vypočítali některé přesné hranice chyb a navrhli metodu pro výběr hodnoty k pro získání požadované hranice chyby. Takové hranice mohou být například použity pro generování pravděpodobných prvočísel. Neměly by se však používat k testování prvočísel neznámého původu, protože v kryptografických systémech se cracker může pokusit nahradit pseudoprvočíslo, když je prvočíslo vyžadováno. V takových případech se lze spolehnout pouze na chybu 4 − k .

Obtížnost práce

Za předpokladu, že čas násobení je logaritmický, při použití rychlého násobení modulo je složitost algoritmu , kde je počet kol. Doba běhu algoritmu je tedy polynomiální. $O(k\log^3n)$ $k$

Pomocí FFT je však možné zkrátit dobu běhu algoritmu na . V tomto případě, pokud vezmeme , kde n je číslo, které se má zkontrolovat, pak se složitost algoritmu rovná . [jedenáct] $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)$

Silně pseudoprimes

Je-li číslo a svědkem jednoduchosti složeného lichého čísla n podle Millera, pak číslo n je zase silně pseudo prvočíslo v základu a . Je-li číslo n silně pseudoprvo v základu a , pak je také Fermatovo pseudoprvo v základu a a Euler-Jacobiho pseudoprvo v základu a . [3]

Například silně pseudoprimes v základu 2 tvoří sekvenci:

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

a v základu 3 sekvence:

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

Poznámky

↑ Miller, 1975 .
↑ 12 Rabin , 1980 .
↑ 1 2 Menezes, Oorschot, Vanstone, 1996 , pp. 141.
↑ Kormen, 2015 , str. 147.
↑ 1 2 Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algoritmy: konstrukce a analýza. - 3. - Moskva: Williams, 2013. - S. 1012-1015. — 1328 s. - ISBN 978-5-8459-1794-2 .
↑ Schoof, 2008 .
↑ Monier, 1980 .
↑ Arnault, 1995 .
↑ Baillie, Wagstaff, 1980 .
↑ Damgård, Landrock, Pomerance, 1993 .
↑ Bruce Schneier. Aplikovaná kryptografie. - Moskva: Triumf, 2013. - S. 298. - 816 s.

Literatura

Miller G. Riemann's Hypothesis and Tests for Primality // STOC '75 :ze sedmého výročního sympozia ACM o teorii výpočetní techniky - New York, NY, USA : ACM , 1975. - S. 234-239. doi : 10.1145/800116.803773
Rabin M. O. Pravděpodobnostní algoritmus pro testování primality // J. Number Theor. / D. Goss - Elsevier BV , 1980. - Sv. 12, Iss. 1. - S. 128-138. — ISSN 0022-314X ; 1096-1658 – doi:10.1016/0022-314X(80)90084-0
Baillie R. , Samuel S. Wagstaff, Jr. Lucas Pseudoprimes (anglicky) // Math. Comp. - AMS , 1980. - Sv. 35, Iss. 152. - S. 1391-1417. — ISSN 0025-5718 ; 1088-6842 – doi:10.1090/S0025-5718-1980-0583518-6
Monier L. Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms (anglicky) // Theoretical Computer Science - Elsevier BV , 1980. - Vol. 12, Iss. 1. - S. 97-108. — ISSN 0304-3975 ; 1879-2294 – doi:10.1016/0304-3975(80)90007-9
Damgård I. , Landrock P. , Pomerance C. Odhady průměrné velikosti případu pro test silné pravděpodobnosti prvočísla // Matematika . Comp. - AMS , 1993. - Sv. 61, Iss. 203. - S. 177-194. — ISSN 0025-5718 ; 1088-6842 – doi:10.2307/2152945
Arnault F. Constructing Carmichael Numbers that are Strong Pseudoprimes to několika bází // Journal of Symbolic Computation - Elsevier BV , 1995. - Vol. 20, Iss. 2. - S. 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 (anglicky) - CRC Press , 1996. - 816 s. — ( Diskrétní matematika a její aplikace ) — ISBN 978-0-8493-8523-0
Schoof R. Four Primality Testing Algorithms (anglicky) // Algorithmic Number Theory : Lattices, Number Fields, Curves and Cryptography / J. P. Buhler , P. Stevenhagen - Cambridge : Cambridge University Press , 2008. - S. 69-81. - ( Publikace výzkumného ústavu Mathematical Sciences ; Vol. 44) - ISBN 978-0-521-80854-5
Kormen T. H. Algorithms : Úvodní kurz / přel. I. Krasikov - M . : Williams , 2015. - 208 s. — ISBN 978-5-8459-1868-0 , 978-5-8459-2073-7

Odkazy

Yu. V. Nesterenko. Kapitola 4.4. Jak rozlišit složené číslo od jednoduchého // Úvod do kryptografie / Ed. V. V. Jaščenko. - Petr, 2001. - 288 s. - ISBN 5-318-00443-1 . Archivováno 25. února 2008 na Wayback Machine
Příklady implementace algoritmu v mnoha programovacích jazycích
S. B. Gaškov. Zjednodušené odůvodnění pravděpodobnostního Miller-Rabinova testu pro testování primality čísel .
Weisstein, Eric W. Rabin-Miller Strong Pseudoprime Test (anglicky) na webu Wolfram MathWorld .
"SPRP záznamy"
Crandall, R. a Pomerance, C. Pravděpodobná prvočísla a svědci // Prvočísla. - Springer-Verlag, 2001. - ISBN 978-0387252827 .

Slovníky a encyklopedie	Britannica (online)

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin