Miller test (talteori)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 6. oktober 2016; checks kræver 9 redigeringer .

Miller-testen er en deterministisk polynomiel primalitetstest foreslået af Miller og først offentliggjort i 1976 [1] .

Beskrivelse af algoritmen

Sådan virker det

Miller-testen er baseret på det faktum, at et ulige sammensat tal enten er en potens af et eller andet primtal, eller der er et primtal, der ligger i intervallet fra til en eller anden funktion afhængig af , hvilket ikke er et vidne til Millers enkelhed af dette. nummer. $n$ $2$ $f(n)$ $n$

Algoritme

Input : n > 2, et ulige naturligt tal, der skal testes for primalitet; Output : composite , betyder at n er et sammensat tal; primtal betyder, at n er et primtal. (1) Tjek, om n er en potens af et tal. hvis det er, så returner det sammensatte (2) Find de første m primtal , hvor m er sådan at Beregn og sådan at og er ulige

p_1, ..., p_m

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

s

q

n-1=q\cdot 2^s

q

Sæt spring til trin (4)

i=1

(3) hvis , så hvis , så returner primtal (4) hvis , returner derefter det sammensatte Beregn (5) hvis returner derefter det sammensatte (6) hvis derefter gå til trin (3)

jeg 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

Sæt (7) hvis derefter gå til trin (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 ) returkomposit

Historie og ændringer

Denne primalitetstest blev foreslået af Gary Miller i 1976 og blev først offentliggjort i Journal of Computer and System Sciences . Den bygger på Ankenys arbejde med at finde den mindste ikke-rest , baseret på den generaliserede Riemann-hypotese (til generaliseringer af zeta-funktioner, kaldet Dirichlet L-funktioner). [2] .

Hvis man antager gyldigheden af den generaliserede Riemann-hypotese, er det i øjeblikket (2016) bevist, at vi kan tage . Det vil sige, at for et tal, der kontrolleres for enkelhed, er det nødvendigt at kontrollere, at det er stærkt pseudo-prime for alle prime baser mindre end, i dette tilfælde, tallet er prime, hvis den generaliserede Riemann hypotese også er sand. $f(n)$ $2\cdot ln^{2}(n)$ $n$ $2\cdot ln^{2}(n)$ $n$

Til at begynde med blev det samme resultat bevist for , men senere i 1985 reducerede Eric Bach3] koefficienten til $70\cdot ln^{2}(n)$

Men selvom funktionen bruges , er Miller-algoritmen mange størrelsesordener langsommere end den probabilistiske Miller-Rabin-algoritme. Den eneste fordel ved denne algoritme (Miller) er, at den pålideligt fastslår primeness af et tal, kun afhængig af den generaliserede Riemann-hypotese. Og denne hypotese, selvom den ikke er bevist indtil videre, men der er stor sandsynlighed, såvel som en masse numeriske beviser til fordel for, at det er sandt. $2\cdot ln^{2}(n)$

Der er også en endnu stærkere formodning understøttet af adskillige teoremer og heuristiske skøn. den øvre grænse blev senere foreslået AlfordGranville og

Hvis et tal er stærkt pseudoprime i alle prime baser mindre end $n$ , så er tallet prime. Denne hypotese er dog ikke blevet bevist indtil videre (2016), selv under antagelsen af den generaliserede Riemann-hypotese. Måske senere, når den generaliserede Riemann-hypotese er bevist, og dette, endnu stærkere resultat, så vil algoritmen, der kontrollerer et tals primalitet ved denne betingelse, være den hurtigste beviste, pålidelige algoritme til at kontrollere et tal for primalitet. For at kontrollere for eksempel et -bit-tal for primeness (dvs. ), behøver du kun at sikre dig, at det er stærkt pseudoprime i alle prime-baser mindre end , hvilket er en hel del sammenlignet med estimatet , i Millers algoritme: vi ville tjekke af alle simple årsager op til . Algoritmen har en polynomisk kompleksitet, da med en stigning i størrelsen (målet) af inputdataene: længden af posten , antallet, der kontrolleres (i ethvert talsystem), vokser beregningskompleksiteten med væksthastigheden af en polynomium af en vis grad fra . (I tilfælde af kontrol for enkelhed eller faktorisering accepterer algoritmerne kun et tal, og størrelsen af inputdataene kan tallet ikke være: størrelsen af dataene er nøjagtigt længden af posten i et eller andet talsystem). $(\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 tjekker for alle prime-baser mindre end , er allerede lidt langsommere end den sandsynlige Miller-Rabin-algoritme (det vil sige, den kan bruges ret praktisk), men den har en klar fordel i forhold til den. Miller-Rabin-algoritmen er altid eksplicit probabilistisk, det vil sige, det vil aldrig være muligt at vide med sikkerhed, at ethvert tal, han modtager , er primtal. Og denne algoritme er højst sandsynligt pålidelig, kun dette skal stadig bevises. (Og selv hvis det viser sig, at den generaliserede Riemann-hypotese er forkert, og så vil Miller-algoritmen være sandsynlighed, men den vil bestemme primiteten af et tal, med en større sandsynlighed end implementeringer af Miller-Rabin-algoritmen. Fordi den sandsynlige Miller-Rabin-algoritmen blev faktisk foreslået som en forenklet version af Miller-algoritmen for at øge hastigheden af beregninger). At finde præcis den mest pålidelige, og samtidig den hurtigste algoritme til at bestemme enkelheden af vilkårlige tal, kan være nyttig i matematiske teorier, der studerer virkelige primtal, og ikke sandsynlige tal. $(\ln n\ln \ln n)/\ln 2$

Ovenstående verifikationsbetingelser er defineret for vilkårligt store primtal, og for faste tal er resultaterne kendte (for 2016), ifølge hvilke tallene

$n<=10^{36}$ , kan du tjekke for enkelhed, endnu hurtigere . Nogle af dem er givet nedenfor som et eksempel (for dem bruger vi den samme klassiske Miller-algoritme, men med et meget lille antal baser):

et tal n < 2047 er primtal, hvis det er stærkt pseudoprimt i baserne a = 2;
et tal n < 1 373 653 er primtal, hvis det er stærkt pseudoprimtal i forhold til baserne a = 2, 3;
et tal n < 25 326 001 er primtal, hvis det er stærkt pseudoprimt i baserne a = 2, 3, 5;
et tal n < 3 215 031 751 er primtal, hvis det er stærkt pseudoprimt i baserne a = 2, 3, 5, 7;
et tal n < 2 152 302 898 747 er primtal, hvis det er stærkt pseudoprimt i baserne a = 2, 3, 5, 7, 11;
et tal n < 3 474 749 660 383 er primtal, hvis det er stærkt pseudoprimt i baserne a = 2, 3, 5, 7, 11, 13;
et tal n < 341 550 071 728 321 er primtal, hvis det er stærkt pseudoprimt i baserne a = 2, 3, 5, 7, 11, 13, 17;
et tal n < 3 825 123 056 546 413 051 er primtal, hvis det er stærkt pseudoprimt i baserne a = 2, 3, 5, 7, 11, 13, 17, 19, 23;
et tal n < 318665857834031151167461 er primtal, hvis det er stærkt pseudoprimt i baserne a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37;
et tal n < 3 317 044 064 679 887 385 961 981 er prime, hvis det er stærkt pseudoprime i baserne a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 1, 3, 1, 1;
...
et tal n < 1 543 267 864 443 420 616 877 677 640 751 301 er prime, hvis det er stærkt pseudoprime i alle prime baser fra 2 til 61 inklusive;
Et tal er prime, hvis det er stærkt pseudoprime med hensyn til alle prime baser fra 2 til 71 inklusive. $n<=10^{36}$

Det første sammensatte tal , som er stærkt pseudoprimtal i alle primtal til og med 71, er endnu ikke fundet, men det vides, at . $n$ $n>10^{36}$

Det vil sige, det er kendt (fra og med 2016), at alle tal mindre end , som er stærkt pseudo-primtal, af de første 20 baser (op til 71 inklusive) også er primtal . $10^{36}$

Fra disse data kan vi se, at de første naturlige tal kan kontrolleres for enkelhed (i øvrigt pålideligt, da dette allerede er blevet bevist ), ved hjælp af antallet af baser, endnu mindre end i alle ovenstående estimater. Denne algoritme er den hurtigste til at kontrollere tal for primalitet. $10^{36}$

Det omvendte udsagn er følgende - hvis et tal er primtal, så er det stærkt pseudo-primtal, generelt, af alle årsager.

Der er også en version af algoritmen, der ikke bruger den udvidede Riemann-hypotese. Denne algoritme har eksponentiel beregningskompleksitet. I dette tilfælde er funktionens rolle funktionen . $f(n)$ $c\cdot n^{\tfrac {1}{1+4\sqrt e}} \ca. c\cdot n^{0{,}133}$

Egenskaber

Determinisme : Testen er deterministisk, hvilket betyder, at for samme n vil resultatet altid være det samme. Heri adskiller den sig for eksempel fra dens modifikation, Miller-Rabin-testen , som er sandsynlig.
Polynomium : Testens køretid afhænger højst polynomielt af bitlængden af n , som sammenligner positivt med brute force, Fermats test eller Eratosthenes' sigte . Testudførelseshastigheden er dog størrelsesordener langsommere end Miller-Rabin-testen .
Betingelse : I hovedversionen af algoritmen er testen baseret på den ubeviste udvidede Riemann-hypotese , det vil sige, at den er betinget. Denne test adskiller sig fra Agrawal-Kayal-Saxena-testen , som er fuldt bevist (og også er deterministisk og polynomiel). Der er også en ubetinget version af algoritmen, men den er meget langsommere end den vigtigste.

Åbningstider

I det tilfælde, hvor den øvre grænse for opregningen er givet af funktionen , kontrollerer algoritmen deterministisk primiteten af tallet n for [4] , men algoritmen er baseret på den generaliserede Riemann-hypotese. Enkelt sagt vokser kompleksiteten af algoritmen hurtigere end , (antallet af baser, der skal kontrolleres for pseudo-enkelhed), fordi jo større basen er, jo mere tidskrævende dens analyse. Fra størrelsen (målet) af inputdataene: længden af posten , antallet, der kontrolleres , afhænger kompleksiteten af algoritmen af følgende: , det vil sige polynomisk kompleksitet, 4. grad. $f(n)=2\cdot ln^{2}(n)$ $O(ln^{4}(n))$ $O(ln^{2}(n))$ $m$ $n$ $O(m^{4})$

I tilfældet når , estimeres den værst tænkelige køretid til [4] . Fra størrelsen af inputdataene: længden af posten , antallet der kontrolleres , kompleksiteten af algoritmen afhænger af: , det vil sige den eksponentielle kompleksitet af graden 1/7. Denne algoritme er meget mere kompliceret: alle eksponentielle algoritmer, med en tilstrækkelig stor størrelse af inputdata, bliver væsentligt mere tidskrævende end alle polynomielle algoritmer. $f(n)=n^{0,133}$ $O(n^{1/7})$ $m$ $n$ $O(e^{m/7})$

Et eksempel på implementering af algoritmen

Et eksempel på implementering af algoritmen, i programmeringssproget C# (.NET Framework 3.5, 4.0).

Dette er blot et af eksemplerne, og maxChecked- variablen kan defineres forskelligt, og ved formlen fra det tal, der kontrolleres (den klassiske Miller-test), og ved de nøjagtige værdier for tal mindre end beskrevet ovenfor, og generelt på en vilkårlig måde, så implementeringen af algoritmen vil vise sig Miller-Rabin. $2\cdot ln^{2}(n)$ $10^{36}$

public bool IsPrime_AlgMiller ( BigInteger checkingNum ) { // (hvis er en potens af et andet tal) if ( IsPowerOfNumber ( checkingNum )) returner false ; BigInteger logN = nyt BigInteger ( BigInteger . Log ( checkingNum )); BigInteger loglogN = nyt BigInteger ( BigInteger . Log ( logN )); BigInteger maxChecked = logN * loglogN / ( nyt BigInteger ( BigInteger . Log ( 2 ))); // maxChecked: fik den maksimale base for at kontrollere for stærk pseudosenkelhed. Dette er et eksempel. BigInteger baseCurrent = nyt BigInteger ( 2 ); bool isPrime = sand ; while ( baseCurrent <= maxChecked ) { // (hvis ikke stærkt pseudoprime i denne base) if (! IsStrongPseudoPrime ( checkingNum , baseCurrent )) { // (så er tallet ikke primetal) isPrime = false ; bryde ; } baseCurrent = NextPrime ( baseCurrent ); } returnere er Prime ; } public bool IsStrongPseudoPrime ( BigInteger checkingNum , BigInteger baseCurrent ) { BigInteger exp = checkingNum - 1 ; // (exp vil ændre sig, og kontrol af resten -1 svarer til at kontrollere resten (checkingNum - 1)) BigInteger ost_1 = exp ; BigInteger res = BigInteger . ModPow ( baseCurrent , exp , checkingNum ); if ( res != 1 ) returner falsk ; // (Bestået bedriftsprøve) while ( sand ) { // (lige; første hit vil altid være lige, derefter loop indtil ulige igen) exp = exp / 2 ; // (resten -1 skal altid være markeret) res = BigInteger . ModPow ( baseCurrent , exp , checkingNum ); hvis ( res == ost_1 ) returnerer sandt ; // (blev ulige igen - skal tjekke for 1 mere) if (! exp . IsEven ) { res = BigInteger . ModPow ( baseCurrent , exp , checkingNum ); if ( res . IsOne ) returner true ; bryde ; } } returnere falsk ; } public BigInteger NextPrime ( BigInteger num ) { //... } offentlig 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 er kun at implementere to funktioner -

1) NextPrime, som modtager et tal og returnerer det næste primtal, som er optimalt til kun at finde små primtal. Denne funktion skulle være endnu enklere og hurtigere.

2) IsPowerOfNumber - en lidt mere kompleks funktion, der bestemmer, om det beståede tal er en potens af et andet primtal. Vi skal finde den enklest mulige implementering af denne funktion.

Også,

3) Du kan fremskynde implementeringen af algoritmen ved først at frafiltrere de tilfælde, hvor tallet er deleligt med mulige små divisorer, men hyppigt forekommende divisorer: 2,3,5,7,11... og først derefter udføre den vigtigste tjek ved hjælp af Miller-algoritmen.

I dette tilfælde vil implementeringen af Millers algoritme i det foreslåede eksempel sandsynligvis være den hurtigste, for vilkårlige store tal. Og selve algoritmen hævder, som allerede vist ovenfor, at være den hurtigste pålidelige algoritme til at kontrollere primalitet (hvis den generaliserede Riemann-hypotese er sand).

Denne implementering af algoritmen er blevet testet uden at bruge funktionen IsPowerOfNumber.

Noter

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

Litteratur

Miller, Gary L. Riemanns hypotese og test for primalitet // Journal of Computer and System Sciences. - 1976. - T. 13 , no. 3 . — ISSN 0022-0000 . - doi : 10.1016/S0022-0000(76)80043-8 .
Ankeny NC Den mindste kvadratiske ikke-rest // Annals of Mathematics. - 1952. - T. 55 .
H. Cohen , H. W. Lenstra, Jr. Primality Testing og Jacobi Sums // Mathematics of Computing. - 1984. - T. 42 , no. 165 .
Bach, Erik. Analysemetoder til analyse og design af talteoretiske algoritmer . - Cambridge, MA: MIT Press, 1985. - 48 s. - ISBN 978-0-262-02219-4 .
Vasilenko O. N. Talteoretiske algoritmer i kryptografi. — MTsNMO. - 2003. - ISBN 5-94057_103_4.

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme