Miller test (talteori)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 oktober 2016; kontroller kräver 9 redigeringar .

Miller-testet är ett deterministiskt polynom-primalitetstest som föreslagits av Miller och först publicerades 1976 [1] .

Beskrivning av algoritmen

Hur det fungerar

Miller-testet är baserat på det faktum att ett udda sammansatt tal antingen är en potens av något primtal, eller så finns det ett primtal som ligger i intervallet från till någon funktion beroende på , vilket inte är ett vittne till Millers enkelhet i detta. siffra. $n$ $2$ $f(n)$ $n$

Algoritm

Indata : n > 2, ett udda naturligt tal som ska testas för primalitet; Output : composite , betyder att n är ett sammansatt tal; primtal betyder att n är ett primtal. (1) Kontrollera om n är en potens av något tal. om det är det, returnera sedan den sammansatta (2) Hitta de första m primtal , där m är sådan att Beräkna och sådan att och är udda

p_1, ..., p_m

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

s

q

n-1=q\cdot 2^s

q

Sätt hoppa till steg (4)

i=1

(3) om , sedan om , returnera primtal (4) om , returnera sedan sammansatta Beräkna (5) om returnera sedan sammansatta ( 6) om sedan gå till steg (3)

jag m

i=i+1

jag > 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

Sätt (7) om sedan gå till steg (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) returnera komposit

Historik och ändringar

Detta primalitetstest föreslogs av Gary Miller 1976 och publicerades först i Journal of Computer and System Sciences . Den bygger på Ankenys arbete med att hitta den minsta icke-resten , baserat på den generaliserade Riemann-hypotesen (för generaliseringar av zetafunktioner, kallade Dirichlet L-funktioner). [2] .

Om man antar giltigheten av den generaliserade Riemann-hypotesen, för närvarande (2016), är det bevisat att vi kan ta . Det vill säga, för ett tal som kontrolleras för enkelhetens skull är det nödvändigt att kontrollera att det är starkt pseudoprimtal för alla primtalsbaser mindre än, i detta fall är talet primtal om den generaliserade Riemann-hypotesen också är sann. $f(n)$ $2\cdot ln^{2}(n)$ $n$ $2\cdot ln^{2}(n)$ $n$

Till en början bevisades samma resultat för , men senare 1985 reducerade Eric Bach3] till 2 $70\cdot ln^{2}(n)$

Men även om funktionen används är Miller-algoritmen många storleksordningar långsammare än den probabilistiska Miller-Rabin-algoritmen. Den enda fördelen med denna algoritm (Miller) är att den på ett tillförlitligt sätt fastställer ett tals primeness, endast förlitar sig på den generaliserade Riemann-hypotesen. Och denna hypotes, även om den inte har bevisats hittills, men det finns en stor sannolikhet, liksom en hel del numeriska bevis för att det är sant. $2\cdot ln^{2}(n)$

Det finns också en ännu starkare gissning som stöds av flera teorem och heuristiska uppskattningar. den övre gränsen föreslogs senare AlfordGranville och

Om ett tal är starkt pseudoprime i alla primtalsbaser mindre än $n$ , då är talet primtal. Denna hypotes har dock inte bevisats hittills (2016) ens under antagandet av den generaliserade Riemann-hypotesen. Kanske senare, när den generaliserade Riemann-hypotesen bevisas, och detta, ännu starkare resultat, kommer algoritmen som kontrollerar ett tals primat med detta villkor att vara den snabbaste bevisade, tillförlitliga algoritmen för att kontrollera ett tal för primat. För att till exempel kontrollera ett -bittal för primeness (dvs ), behöver du bara se till att det är starkt pseudoprime i alla prime baser mindre än , vilket är ganska mycket jämfört med uppskattningen , i Millers algoritm: vi skulle kontrollera av alla enkla skäl upp till . Algoritmen har en polynomkomplexitet, eftersom med en ökning av storleken (måttet) på indata: längden på posten , numret som kontrolleras (i valfritt talsystem), växer beräkningskomplexiteten, med tillväxthastigheten för en polynom av någon grad från . (När det gäller att kontrollera för enkelhet eller faktorisering accepterar algoritmerna endast ett tal, och storleken på indata kan numret i sig inte vara: storleken på data är exakt längden på posten i något nummersystem). $(\ln n\ln \ln n)/\ln 2$ $n$ $1024$ $n=2^{1024}$ $6722$ $2\cdot ln^{2}(n)$ $1007582$ $m$ $n$ $m$

Miller-algoritmen, som kontrollerar för alla primbaser mindre än , är redan något långsammare än den probabilistiska Miller-Rabin-algoritmen (det vill säga den kan användas ganska praktiskt), men den har en klar fördel gentemot den. Miller-Rabin-algoritmen är alltid explicit probabilistisk, det vill säga det kommer aldrig att vara möjligt att säkert veta att något tal han får är primtal. Och den här algoritmen är troligen pålitlig, bara detta måste fortfarande bevisas. (Och även om det visar sig att den generaliserade Riemann-hypotesen är fel, och då kommer Miller-algoritmen att vara probabilistisk, men den kommer att bestämma ett tals primeness, med en större sannolikhet än implementeringar av Miller-Rabin-algoritmen. Eftersom den probabilistiska Miller-Rabin-algoritmen föreslogs faktiskt som en förenklad version av Miller-algoritmen för att öka beräkningshastigheten). Att hitta exakt den mest tillförlitliga, och samtidigt den snabbaste algoritmen för att bestämma enkelheten i godtyckliga tal, kan vara användbart i matematiska teorier som studerar verkligt primtal, och inte sannolikhetsberoende. $(\ln n\ln \ln n)/\ln 2$

Ovanstående verifieringsvillkor är definierade för godtyckligt stora primtal, och för fasta tal är resultaten kända (för 2016), enligt vilka talen

$n<=10^{36}$ , kan du kontrollera för enkelheten, ännu snabbare . Några av dem ges nedan som exempel (för dem använder vi samma klassiska Miller-algoritm, men med ett mycket litet antal baser):

ett tal n < 2047 är primtal om det är starkt pseudoprimtal i baserna a = 2;
ett tal n < 1 373 653 är primtal om det är starkt pseudoprimtal med avseende på baserna a = 2, 3;
ett tal n < 25 326 001 är primtal om det är starkt pseudoprim i baserna a = 2, 3, 5;
ett tal n < 3 215 031 751 är primtal om det är starkt pseudoprim i baserna a = 2, 3, 5, 7;
ett tal n < 2 152 302 898 747 är primtal om det är starkt pseudoprim i baserna a = 2, 3, 5, 7, 11;
ett tal n < 3 474 749 660 383 är primtal om det är starkt pseudoprim i baserna a = 2, 3, 5, 7, 11, 13;
ett tal n < 341 550 071 728 321 är primtal om det är starkt pseudoprim i baserna a = 2, 3, 5, 7, 11, 13, 17;
ett tal n < 3 825 123 056 546 413 051 är primtal om det är starkt pseudoprim i baserna a = 2, 3, 5, 7, 11, 13, 17, 19, 23;
ett tal n < 318665857834031151167461 är primtal om det är starkt pseudoprimtal i baserna a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37;
ett tal n < 3 317 044 064 679 887 385 961 981 är primtal om det är starkt pseudoprime i baserna a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 1, 3, 1, 3, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3
...
ett tal n < 1 543 267 864 443 420 616 877 677 640 751 301 är primtal om det är starkt pseudoprime i alla primtalsbaser från 2 till och med 61;
Ett tal är primtal om det är starkt pseudoprime med avseende på alla primtalsbaser från 2 till 71 inklusive. $n<=10^{36}$

Det första sammansatta talet , som är starkt pseudoprimtal i alla primtal till och med 71, har ännu inte hittats, men det är känt att . $n$ $n>10^{36}$

Det vill säga, det är känt (från och med 2016) att alla tal mindre än , som är starkt pseudoprimtal, av de första 20 baserna (upp till 71 inklusive) också är primtal . $10^{36}$

Från dessa data ser vi att de första naturliga talen kan kontrolleras för enkelhet ( dessutom tillförlitligt, eftersom detta redan har bevisats ), med hjälp av antalet baser, ännu mindre än i alla ovanstående uppskattningar. Denna algoritm är den snabbaste för att kontrollera siffror för primalitet. $10^{36}$

Det omvända påståendet är följande - om ett tal är primtal, så är det starkt pseudoprimtal, i allmänhet, av alla skäl.

Det finns också en version av algoritmen som inte använder den utökade Riemann-hypotesen. Denna algoritm har exponentiell beräkningskomplexitet. I det här fallet är funktionens roll funktionen . $f(n)$ $c\cdot n^{\tfrac {1}{1+4\sqrt e}} \approx c\cdot n^{0{,}133}$

Egenskaper

Determinism : Testet är deterministiskt, vilket betyder att för samma n kommer resultatet alltid att vara detsamma. I detta skiljer den sig till exempel från sin modifiering, Miller-Rabin-testet , som är sannolikhet.
Polynom : Testets gångtid beror högst polynomiskt på bitlängden på n , som jämförs med råkraft, Fermats test eller Eratosthenes sikt . Testexekveringshastigheten är dock storleksordningar långsammare än för Miller-Rabin-testet .
Villkorlighet : I huvudversionen av algoritmen är testet baserat på den obevisade utökade Riemann-hypotesen , det vill säga det är villkorat. Detta test skiljer sig från Agrawal-Kayal-Saxena-testet , som är fullt bevisat (och även är deterministiskt och polynomiskt). Det finns också en ovillkorlig version av algoritmen, men den är mycket långsammare än den huvudsakliga.

Öppettider

I det fall då den övre gränsen för uppräkningen ges av funktionen kontrollerar algoritmen deterministiskt primiteten av numret n för [4] , men algoritmen är baserad på den generaliserade Riemann-hypotesen. Enkelt uttryckt växer algoritmens komplexitet snabbare än , (antalet baser att kontrollera för pseudoenkelhet), eftersom ju större basen är, desto mer tidskrävande analysen. Från storleken (måttet) på indata: längden på posten , antalet som kontrolleras , komplexiteten hos algoritmen beror på följande: , det vill säga polynom komplexitet, 4:e graden. $f(n)=2\cdot ln^{2}(n)$ $O(ln^{4}(n))$ $O(ln^{2}(n))$ $m$ $n$ $O(m^{4})$

I fallet när beräknas den värsta körtiden till [4] . Från storleken på indata: längden på posten , antalet som kontrolleras , komplexiteten hos algoritmen beror på: , det vill säga den exponentiella komplexiteten för graden 1/7. Denna algoritm är mycket mer komplicerad: alla exponentiella algoritmer, med en tillräckligt stor storlek på indata, blir betydligt mer tidskrävande än alla polynomalgoritmer. $f(n)=n^{0,133}$ $O(n^{1/7})$ $m$ $n$ $O(e^{m/7})$

Ett exempel på implementering av algoritmen

Ett exempel på implementering av algoritmen, i programmeringsspråket C# (.NET Framework 3.5, 4.0).

Detta är bara ett av exemplen, och variabeln maxChecked kan definieras på olika sätt, och med formeln från numret som kontrolleras (det klassiska Miller-testet), och med de exakta värdena för siffror mindre än beskrivna ovan, och i allmänhet på ett godtyckligt sätt, så att implementeringen av algoritmen kommer att visa sig Miller-Rabin. $2\cdot ln^{2}(n)$ $10^{36}$

public bool IsPrime_AlgMiller ( BigInteger checkingNum ) { // (if är en potens av ett annat tal) if ( IsPowerOfNumber ( checkingNum )) returnerar false ; BigInteger logN = new BigInteger ( BigInteger . Log ( checkingNum )); BigInteger loglogN = nytt BigInteger ( BigInteger . Log ( logN )); BigInteger maxChecked = logN * loglogN / ( nytt BigInteger ( BigInteger . Log ( 2 ))); // maxChecked: fick den maximala basen för att kontrollera för stark pseudoenkelhet. Detta är ett exempel. BigInteger baseCurrent = nytt BigInteger ( 2 ); bool isPrime = sant ; while ( baseCurrent <= maxChecked ) { // (om inte starkt pseudoprime i denna bas) if (! IsStrongPseudoPrime ( checkingNum , baseCurrent )) { // (då är talet inte primtal) isPrime = false ; bryta ; } baseCurrent = NextPrime ( baseCurrent ); } return isPrime ; } public bool IsStrongPseudoPrime ( BigInteger checkingNum , BigInteger baseCurrent ) { BigInteger exp = checkingNum - 1 ; // (exp kommer att ändras, och att kontrollera resten -1 motsvarar att kontrollera resten (checkingNum - 1)) BigInteger ost_1 = exp ; BigInteger res = BigInteger . ModPow ( basCurrent , exp , checkingNum ); if ( res != 1 ) returnerar falskt ; // (gårdsprovet godkänt) while ( true ) { // (jämn; första träffen kommer alltid att vara jämn, sedan loopa tills udda igen) exp = exp / 2 ; // (resten -1 ska alltid kontrolleras) res = BigInteger . ModPow ( basCurrent , exp , checkingNum ); if ( res == ost_1 ) returnerar sant ; // (blev udda igen - måste leta efter 1 till) if (! exp . IsEven ) { res = BigInteger . ModPow ( basCurrent , exp , checkingNum ); if ( res . IsOne ) returnerar sant ; bryta ; } } returnera falskt ; } 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 ; }

Det återstår att implementera bara två funktioner -

1) NextPrime, som tar emot ett tal och returnerar nästa primtal, vilket är optimalt för att hitta bara små primtal. Denna funktion borde vara ännu enklare och snabbare.

2) IsPowerOfNumber - en något mer komplex funktion som avgör om talet som passeras är en potens av ett annat primtal. Vi måste hitta den enklaste möjliga implementeringen av denna funktion.

Också,

3) Du kan påskynda implementeringen av algoritmen genom att först filtrera bort de fall då talet är delbart med möjliga små divisorer, men ofta förekommande divisorer: 2,3,5,7,11... och först därefter utföra huvuddelen kontrollera med Miller-algoritmen.

I det här fallet är implementeringen av Millers algoritm i det föreslagna exemplet sannolikt den snabbaste, för godtyckliga stora antal. Och själva algoritmen, som redan visats ovan, påstår sig vara den snabbaste tillförlitliga algoritmen för att kontrollera primatitet (om den generaliserade Riemann-hypotesen är sann).

Denna implementering av algoritmen har testats framgångsrikt utan att använda funktionen IsPowerOfNumber.

Anteckningar

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

Litteratur

Miller, Gary L. Riemanns hypotes och tester för primat // Journal of Computer and System Sciences. - 1976. - T. 13 , nr. 3 . — ISSN 0022-0000 . - doi : 10.1016/S0022-0000(76)80043-8 .
Ankeny NC Den minsta kvadratiska icke-resten // Annals of Mathematics. - 1952. - T. 55 .
H. Cohen , H. W. Lenstra, Jr. Primalitetstestning och Jacobi Summor // Mathematics of Computing. - 1984. - T. 42 , nr. 165 .
Bach, Eric. Analytiska metoder i analys och design av talteoretiska algoritmer . - Cambridge, MA: MIT Press, 1985. - 48 sid. - ISBN 978-0-262-02219-4 .
Vasilenko O. N. Talteoretiska algoritmer i kryptografi. — MTsNMO. - 2003. - ISBN 5-94057_103_4.

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm