Millerův test (teorie čísel)

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é 6. října 2016; kontroly vyžadují 9 úprav .

Millerův test je deterministický polynomiální test primality navržený Millerem a poprvé publikovaný v roce 1976 [1] .

Popis algoritmu

Jak to funguje

Millerův test je založen na skutečnosti, že liché složené číslo je buď mocninou nějakého prvočísla, nebo existuje prvočíslo ležící v intervalu od do nějaké funkce v závislosti na , což není svědkem Millerovy jednoduchosti tohoto číslo. $n$ $2$ $f(n)$ $n$

Algoritmus

Vstup : n > 2, liché přirozené číslo, které má být testováno na primálnost; Výstup : kompozitní , znamená, že n je složené číslo; prvočíslo znamená, že n je prvočíslo. (1) Zkontrolujte, zda n je mocninou nějakého čísla. pokud ano , pak vraťte kompozit (2) Najděte prvních m prvočísel , kde m je takové, že Vypočítejte a takové, že a je liché

p_1, ..., p_m

p_m \le f(n) \le p_{m+1}

s

q

n-1=q\cdot 2^s

q

Přesuňte skok na krok (4)

i=1

(3) if , then if , then vraťte prvočíslo (4) if , pak vraťte kompozit Vypočítejte (5) if potom vraťte kompozit (6) if pak přejděte ke kroku (3)

já m

i=i+1

i > m

p_i|n

p_i^q \bmod n, p_i^{q\cdot 2}\bmod n, ..., p_i^{q\cdot 2^s}\bmod n

p_i^{q\cdot 2^s}\bmod n \ne 1

p_i^{q}\bmod n = 1

Vložte (7) , pokud, přejděte ke kroku (3)

j = \max(j:p_i^{q \cdot 2^j}\bmod n \ne 1)

p_i^{q\cdot 2^j}\bmod n = n-1

(8) návratový kompozit

Historie a úpravy

Tento test primality navrhl Gary Miller v roce 1976 a byl poprvé publikován v Journal of Computer and System Sciences . Staví na Ankenyho práci na nalezení nejmenšího nezbytku , na základě zobecněné Riemannovy hypotézy (pro zobecnění zeta funkcí, nazývané Dirichletovy L-funkce). [2] .

Za předpokladu platnosti zobecněné Riemannovy hypotézy je v tuto chvíli (2016) prokázáno, že můžeme vzít . To znamená, že u čísla, které je kontrolováno pro jednoduchost, je nutné zkontrolovat, že je silně pseudoprvočíslo pro všechny základy prvočísel menší než v tomto případě číslo je prvočíslo, pokud platí i zobecněná Riemannova hypotéza. $f(n)$ $2\cdot ln^{2}(n)$ $n$ $2\cdot ln^{2}(n)$ $n$

Zpočátku byl stejný výsledek prokázán pro , ale později v roce 1985 Eric Bach snížil 3] na 2 $70\cdot ln^{2}(n)$

Nicméně, i když je funkce použita , je Millerův algoritmus o mnoho řádů pomalejší než pravděpodobnostní Miller-Rabinův algoritmus. Jedinou výhodou tohoto algoritmu (Miller) je to, že spolehlivě stanoví prvočíslo čísla, přičemž se opírá pouze o zobecněnou Riemannovu hypotézu. A tato hypotéza sice zatím není prokázána, ale je zde vysoká pravděpodobnost, stejně jako mnoho číselných důkazů ve prospěch toho, že je pravdivá. $2\cdot ln^{2}(n)$

Existuje také ještě silnější domněnka podpořená několika teorémy a heuristickými odhady. horní bylo navrženo AlfordemGranvillem a Pomerancem

Pokud je číslo silně pseudoprvočíslo ve všech základních základech menší než $n$ , pak je číslo prvočíslo. Tato hypotéza však nebyla doposud (2016) prokázána ani za předpokladu zobecněné Riemannovy hypotézy. Možná později, až bude dokázána zobecněná Riemannova hypotéza a tento, ještě silnější výsledek, pak bude algoritmus, který kontroluje primálnost čísla touto podmínkou, nejrychlejším dokázaným a spolehlivým algoritmem pro kontrolu primálnosti čísla. Chcete-li například zkontrolovat prvočíslo -bitového čísla (tj. ), musíte se pouze ujistit, že je silně pseudoprvočíslo ve všech základních základech nižší než , což je v Millerově algoritmu poměrně málo ve srovnání s odhadem : zkontrolovali bychom ze všech jednoduchých důvodů až do . Algoritmus má polynomiální složitost, protože s rostoucí velikostí (mírou) vstupních dat: délka záznamu , kontrolované číslo (v libovolném číselném systému) roste výpočetní složitost s rychlostí růstu a polynom určitého stupně od . (V případě kontroly jednoduchosti nebo faktorizace algoritmy akceptují pouze číslo a velikost vstupních dat samotné číslo nemůže být: velikost dat je přesně délkou záznamu v nějaké číselné soustavě). $(\ln n\ln \ln n)/\ln 2$ $n$ $1024$ $n=2^{1024}$ $6722$ $2\cdot ln^{2}(n)$ $1007582$ $m$ $n$ $m$

Millerův algoritmus, který kontroluje všechny prvočísla menší než , je již o něco pomalejší než pravděpodobnostní Miller-Rabinův algoritmus (to znamená, že jej lze použít zcela prakticky), ale má oproti němu jasnou výhodu. Miller-Rabinův algoritmus je vždy explicitně pravděpodobnostní, to znamená, že nikdy nebude možné s jistotou vědět, že jakékoli číslo, které obdrží, je prvočíslo. A tento algoritmus je s největší pravděpodobností spolehlivý, jen to ještě musí být prokázáno. (A i když se ukáže, že zobecněná Riemannova hypotéza je chybná, a pak bude Millerův algoritmus pravděpodobnostní, ale určí prvočíslost čísla s větší pravděpodobností než implementace Miller-Rabinova algoritmu. Protože pravděpodobnostní Miller-Rabinův algoritmus byl navržen ve skutečnosti jako zjednodušená verze Millerova algoritmu za účelem zvýšení rychlosti výpočtů). Nalezení přesně nejspolehlivějšího a zároveň nejrychlejšího algoritmu pro určení jednoduchosti libovolných čísel může být užitečné v matematických teoriích, které studují skutečně prvočísla, a ne pravděpodobnostní. $(\ln n\ln \ln n)/\ln 2$

Výše uvedené ověřovací podmínky jsou definovány pro libovolně velká prvočísla a pro pevná čísla jsou známy výsledky (pro rok 2016), podle kterých se čísla

$n<=10^{36}$ , můžete zkontrolovat jednoduchost, ještě rychleji . Některé z nich jsou uvedeny níže jako příklad (pro ně používáme stejný klasický Millerův algoritmus, ale s velmi malým počtem bází):

číslo n < 2047 je prvočíslo, pokud je silně pseudoprvočíslo v základech a = 2;
číslo n < 1 373 653 je prvočíslo, pokud je silně pseudoprvočíslo vzhledem k bázím a = 2, 3;
číslo n < 25 326 001 je prvočíslo, pokud je silně pseudoprvočíslo v základech a = 2, 3, 5;
číslo n < 3 215 031 751 je prvočíslo, pokud je silně pseudoprvočíslo v základech a = 2, 3, 5, 7;
číslo n < 2 152 302 898 747 je prvočíslo, pokud je silně pseudoprvočíslo v základech a = 2, 3, 5, 7, 11;
číslo n < 3 474 749 660 383 je prvočíslo, pokud je silně pseudoprvočíslo v základech a = 2, 3, 5, 7, 11, 13;
číslo n < 341 550 071 728 321 je prvočíslo, pokud je silně pseudoprvočíslo v základech a = 2, 3, 5, 7, 11, 13, 17;
číslo n < 3 825 123 056 546 413 051 je prvočíslo, pokud je silně pseudoprvočíslo v základech a = 2, 3, 5, 7, 11, 13, 17, 19, 23;
číslo n < 318665857834031151167461 je prvočíslo, pokud je silně pseudoprvočíslo v základech a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37;
číslo n < 3 317 044 064 679 887 385 961 981 je prvočíslo, pokud je silně pseudoprvočíslo v základech a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37;
...
číslo n < 1 543 267 864 443 420 616 877 677 640 751 301 je prvočíslo, pokud je silně pseudoprvočíslo ve všech základech prvočísel od 2 do 61 včetně;
Číslo je prvočíslo, pokud je silně pseudoprvočíslo vzhledem ke všem prvočíslům od 2 do 71 včetně. $n<=10^{36}$

První složené číslo , které je silně pseudoprvočíslo ve všech prvočíslech do 71 včetně, zatím nebylo nalezeno, ale je známo, že . $n$ $n>10^{36}$

To znamená, že je známo (od roku 2016), že všechna čísla menší než , která jsou silně pseudoprvočísla, o prvních 20 bází (až do 71 včetně) jsou také prvočísla . $10^{36}$

Z těchto dat vidíme, že první přirozená čísla lze pro jednoduchost ( navíc spolehlivě, protože to již bylo prokázáno ) ověřit pomocí počtu bází ještě méně než ve všech výše uvedených odhadech. Tento algoritmus je nejrychlejší pro kontrolu prvořadosti čísel. $10^{36}$

Opačné tvrzení je následující - je-li číslo prvočíslo, pak je silně pseudoprvočíslo, obecně ze všech důvodů.

Existuje také verze algoritmu, která nepoužívá rozšířenou Riemannovu hypotézu. Tento algoritmus má exponenciální výpočetní složitost. V tomto případě je rolí funkce funkce . $f(n)$ $c\cdot n^{\tfrac {1}{1+4\sqrt e}} \approx c\cdot n^{0{,}133}$

Vlastnosti

Determinismus : Test je deterministický, což znamená, že pro stejné n bude výsledek vždy stejný. V tom se liší například od své modifikace, Miller-Rabinova testu , který je pravděpodobnostní.
Polynom : Průběh testu závisí nanejvýš polynomiálně na bitové délce n , která je srovnatelná s hrubou silou, Fermatovým testem nebo Eratosthenovým sítem . Rychlost provádění testu je však řádově nižší než u Miller-Rabinova testu .
Podmíněnost : V hlavní verzi algoritmu je test založen na neprokázané rozšířené Riemannově hypotéze , to znamená, že je podmíněný. Tento test se liší od testu Agrawal-Kayal-Saxena , který je plně prokázán (a je také deterministický a polynomiální). Existuje také bezpodmínečná verze algoritmu, ale je mnohem pomalejší než hlavní.

Otevírací doba

V případě, že horní mez výčtu je dána funkcí , algoritmus deterministicky kontroluje prvočíslost čísla n pro [4] , ale algoritmus je založen na zobecněné Riemannově hypotéze. Jednoduše řečeno, složitost algoritmu roste rychleji než , (počet bází pro kontrolu pseudojednoduchosti), protože čím větší je báze, tím je její analýza časově náročnější. Z velikosti (míry) vstupních dat: délka záznamu , kontrolované číslo , složitost algoritmu závisí na následujícím: , tedy polynomiální složitost, 4. stupeň. $f(n)=2\cdot ln^{2}(n)$ $O(ln^{4}(n))$ $O(ln^{2}(n))$ $m$ $n$ $O(m^{4})$

V případě kdy , nejhorší případ běhu se odhaduje jako [4] . Z velikosti vstupních dat: délka záznamu , kontrolované číslo , složitost algoritmu závisí na: , tedy exponenciální složitosti stupně 1/7. Tento algoritmus je mnohem složitější: všechny exponenciální algoritmy s dostatečně velkou velikostí vstupních dat jsou výrazně časově náročnější než všechny polynomiální algoritmy. $f(n)=n^{0,133}$ $O(n^{1/7})$ $m$ $n$ $O(e^{m/7})$

Příklad implementace algoritmu

Příklad implementace algoritmu v programovacím jazyce C# (.NET Framework 3.5, 4.0).

Toto je jen jeden z příkladů a proměnná maxChecked může být definována odlišně, a to vzorcem z kontrolovaného čísla (klasický Millerův test) a přesnými hodnotami pro čísla menší, než je popsáno výše, a obecně libovolným způsobem, takže implementace algoritmu dopadne Miller-Rabin. $2\cdot ln^{2}(n)$ $10^{36}$

public bool IsPrime_AlgMiller ( BigInteger checkingNum ) { // (pokud je mocninou jiného čísla) if ( IsPowerOfNumber ( checkingNum )) return false ; BigInteger logN = new BigInteger ( BigInteger . Log ( checkingNum )); BigInteger loglogN = new BigInteger ( BigInteger . Log ( logN )); BigInteger maxChecked = logN * loglogN / ( new BigInteger ( BigInteger . Log ( 2 ))); // maxChecked: získal maximální základ pro kontrolu silné pseudojednoduchosti. Toto je jeden příklad. BigInteger baseCurrent = new BigInteger ( 2 ); bool isPrime = true ; while ( baseCurrent <= maxChecked ) { // (pokud není silně pseudoprime v této bázi) if (! IsStrongPseudoPrime ( checkingNum , baseCurrent )) { // (pak číslo není prvočíslo) isPrime = false ; zlomit ; } baseCurrent = NextPrime ( baseCurrent ); } return isPrime ; } public bool IsStrongPseudoPrime ( BigInteger checkingNum , BigInteger baseCurrent ) { BigInteger exp = checkingNum - 1 ; // (exp se změní a kontrola zbytku -1 je ekvivalentní kontrole zbytku (checkingNum - 1)) BigInteger ost_1 = exp ; BigInteger res = BigInteger . ModPow ( baseCurrent , exp , checkingNum ); if ( res != 1 ) return false ; // (Úspěšně test na farmě) while ( true ) { // (sudý; první zásah bude vždy sudý, poté smyčka, dokud znovu lichá) exp = exp / 2 ; // (zbytek -1 by měl být vždy zaškrtnut) res = BigInteger . ModPow ( baseCurrent , exp , checkingNum ); if ( res == ost_1 ) return true ; // (znovu se stalo lichým - je třeba zkontrolovat 1 další) if (! exp . IsEven ) { res = BigInteger . ModPow ( baseCurrent , exp , checkingNum ); if ( res . IsOne ) return true ; zlomit ; } } vrátit false ; } public BigInteger NextPrime ( BigInteger num ) { //... } public bool IsPowerOfNumber ( BigInteger n ) // n=p^k => p-1|n-1 && 2^(p-1)=1(mod p) => 2^(n-1)=1(mod p) => p|2^(n-1)-1 => p|gcd(2^(n-1)-1,n) { return BigInteger . GreatestCommonDivisor ( BigInteger . ModPow ( 2 , n - 1 , n ) - 1 , n ) > 1 ; }

Zbývá implementovat pouze dvě funkce -

1) NextPrime, který přijme číslo a vrátí další prvočíslo, což je optimální pro hledání právě malých prvočísel. Tato funkce by měla být ještě jednodušší a rychlejší.

2) IsPowerOfNumber - o něco složitější funkce, která určuje, zda je předané číslo mocninou jiného, prvočísla. Musíme najít co nejjednodušší implementaci této funkce.

Taky,

3) Implementaci algoritmu můžete urychlit tak, že nejprve odfiltrujete případy, kdy je číslo dělitelné možnými malými děliteli, ale často se vyskytujícími děliteli: 2,3,5,7,11... a teprve poté provedete hlavní zkontrolovat pomocí Millerova algoritmu.

V tomto případě bude implementace Millerova algoritmu v navrhovaném příkladu pravděpodobně nejrychlejší pro libovolně velká čísla. A samotný algoritmus, jak již bylo ukázáno výše, tvrdí, že je nejrychlejším spolehlivým algoritmem pro kontrolu primality (pokud je zobecněná Riemannova hypotéza pravdivá).

Tato implementace algoritmu byla úspěšně testována bez použití funkce IsPowerOfNumber.

Poznámky

↑ Miller, Gary L, 1976, s. 300-317
↑ Ankeny N. C, 1952, s. 65-72
↑ Bach a Eric, 1985
↑ 1 2 Vasilenko O.N., 2003, str. 32-37

Literatura

Miller, Hypotéza a testy primality Garyho L. Riemanna // Journal of Computer and System Sciences. - 1976. - T. 13 , no. 3 . — ISSN 0022-0000 . - doi : 10.1016/S0022-0000(76)80043-8 .
Ankeny NC Nejméně kvadratické nezbytky // Annals of Mathematics. - 1952. - T. 55 .
H. Cohen , H. W. Lenstra, Jr. Testování primality a Jacobiho součty // Matematika počítání. - 1984. - T. 42 , no. 165 .
Bach, Eric. Analytické metody v analýze a návrhu číselně teoretických algoritmů . - Cambridge, MA: MIT Press, 1985. - 48 s. - ISBN 978-0-262-02219-4 .
Vasilenko O. N. Číselné teoretické algoritmy v kryptografii. — MTsNMO. - 2003. - ISBN 5-94057_103_4.

Čí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