Millerin testi (lukuteoria)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6. lokakuuta 2016 tarkistetusta versiosta . tarkastukset vaativat 9 muokkausta .

Millerin testi on Millerin ehdottama deterministinen polynomiprimaliteettitesti , joka julkaistiin ensimmäisen kerran vuonna 1976 [1] .

Algoritmin kuvaus

Kuinka se toimii

Millerin testi perustuu siihen tosiasiaan, että pariton yhdistelmäluku on joko jonkin alkuluvun potenssi tai välissä on alkuluku jostain funktiosta riippuen , mikä ei todista tämän Millerin yksinkertaisuutta . määrä. $n$ $2$ $f(n)$ $n$

Algoritmi

Syöte : n > 2, pariton luonnollinen luku, joka testataan primaalisuuden suhteen; Tulos : komposiitti tarkoittaa, että n on yhdistelmäluku; alkuluku tarkoittaa, että n on alkuluku. (1) Tarkista, onko n jonkin luvun potenssi. jos on, niin palauta komposiitti (2) Etsi ensimmäiset m alkulukua , jossa m on sellainen, että Laske ja sellainen, että ja on pariton

p_1, ..., p_m

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

s

q

n-1=q\cdot 2^s

q

Siirry vaiheeseen (4)

i=1

(3) jos , niin jos , niin palauta alkuluku (4) jos , niin palauta yhdistelmä Laske (5) jos sitten palauta komposiitti (6) jos sitten siirry vaiheeseen (3)

i\le 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

Laita (7) jos siirry sitten vaiheeseen (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 ) palautuskomposiitti

Historia ja muutokset

Tämän primaalisuustestin ehdotti Gary Miller vuonna 1976 , ja se julkaistiin ensimmäisen kerran Journal of Computer and System Sciences -lehdessä . Se perustuu Ankenyn työhön vähiten ei-jäännöksen löytämiseksi , joka perustuu yleistettyyn Riemannin hypoteesiin (zeta-funktioiden yleistyksiä varten, joita kutsutaan Dirichlet L-funktioiksi). [2] .

Olettaen yleisen Riemannin hypoteesin pätevyyden tällä hetkellä (2016) on todistettu, että voimme ottaa . Toisin sanoen, jos luku tarkistetaan yksinkertaisuuden vuoksi, on tarpeen tarkistaa, että se on vahvasti pseudo-alkuluku kaikille alkukantaisille pienempi kuin tässä tapauksessa luku on alkuluku, jos myös yleistetty Riemannin hypoteesi pitää paikkansa. $f(n)$ $2\cdot ln^{2}(n)$ $n$ $2\cdot ln^{2}(n)$ $n$

Aluksi sama tulos todistettiin , mutta myöhemmin vuonna 1985 Eric Bach pienensi 3] kahteen $70\cdot ln^{2}(n)$

Kuitenkin, vaikka funktiota käytettäisiin , Millerin algoritmi on monta suuruusluokkaa hitaampi kuin todennäköisyyspohjainen Miller-Rabin-algoritmi. Tämän algoritmin (Miller) ainoa etu on, että se määrittää luotettavasti luvun alkuasteen tukeutuen vain yleistettyyn Riemannin hypoteesiin. Ja tämä hypoteesi, vaikka sitä ei ole toistaiseksi todistettu, mutta sillä on suuri todennäköisyys, samoin kuin paljon numeerisia todisteita sen tosiasian puolesta, että se on totta. $2\cdot ln^{2}(n)$

On myös vielä vahvempi olettamus, jota tukevat useat lauseet ja heuristiset estimaatit. Ylärajan ehdottivat AlfordGranville ja Pomerance _

Jos luku on vahvasti pseudoprime kaikissa alkukantoissa, jotka ovat pienempiä kuin $n$ , niin luku on alkuluku. Tätä hypoteesia ei ole kuitenkaan toistaiseksi (2016) todistettu edes yleistetyn Riemannin hypoteesin oletuksella. Ehkä myöhemmin, kun yleistetty Riemannin hypoteesi todistetaan ja tämä vieläkin vahvempi tulos, niin luvun primaalisuuden tällä ehdolla tarkistava algoritmi on nopein todistettu, luotettava algoritmi luvun primaalisuuden tarkistamiseksi. Todellakin, jos haluat tarkistaa esimerkiksi -bitin luvun primeness (eli ), sinun tarvitsee vain varmistaa, että se on vahvasti pseudoalkuluku kaikissa alkukantoissa pienempi kuin , mikä on melko vähän verrattuna Millerin algoritmin estimaatiin: tarkistamme kaikki yksinkertaiset syyt aina . Algoritmilla on polynominen monimutkaisuus, koska syötetietojen koon (mitan) kasvaessa: tietueen pituus, tarkistettava numero (missä tahansa lukujärjestelmässä), laskennallinen monimutkaisuus kasvaa jonkinasteinen polynomi kohteesta . (Yksinkertaisuuden tai tekijöiden tarkistuksen tapauksessa algoritmit hyväksyvät vain luvun, ja syöttötietojen koko, itse luku ei voi olla: datan koko on täsmälleen tietueen pituus jossain numerojärjestelmässä). ${\näyttötyyli (\ln n\ln \ln n)/\ln 2}$ $n$ $1024$ $n=2^{1024}$ $6722$ $2\cdot ln^{2}(n)$ $1007582$ $m$ $n$ $m$

Miller-algoritmi, joka tarkistaa kaikki alkukannat, jotka ovat pienempiä kuin , on jo hieman hitaampi kuin todennäköisyyspohjainen Miller-Rabin-algoritmi (eli sitä voidaan käyttää melko käytännöllisesti), mutta sillä on selkeä etu verrattuna siihen. Miller-Rabin-algoritmi on aina eksplisiittisesti todennäköinen, eli ei koskaan voi tietää varmasti, että mikä tahansa hänen vastaanottama luku on alkuluku. Ja tämä algoritmi on todennäköisesti luotettava, vain tämä on vielä todistettava. (Ja vaikka kävisikin ilmi, että yleistetty Riemannin hypoteesi on väärä, ja silloin Millerin algoritmi on todennäköisyys, mutta se määrittää luvun alkuasteen suuremmalla todennäköisyydellä kuin Miller-Rabin-algoritmin toteutukset. Koska todennäköisyys Miller-Rabin-algoritmia ehdotettiin itse asiassa Miller-algoritmin yksinkertaistetuksi versioksi laskennan nopeuden lisäämiseksi). Täsmälleen luotettavimman ja samalla nopeimman algoritmin löytäminen mielivaltaisten lukujen yksinkertaisuuden määrittämiseksi voi olla hyödyllistä matemaattisissa teorioissa, jotka tutkivat aidosti alkulukuja, ei todennäköisyyksiä. ${\näyttötyyli (\ln n\ln \ln n)/\ln 2}$

Yllä olevat varmennusehdot on määritelty mielivaltaisen suurille alkuluvuille ja kiinteille luvuille tiedetään tulokset (vuodelle 2016), joiden mukaan luvut

$n<=10^{36}$ , voit tarkistaa yksinkertaisuuden, jopa nopeammin . Jotkut niistä on annettu alla esimerkkinä (niille käytämme samaa klassista Millerin algoritmia, mutta hyvin pienellä määrällä emäksiä):

luku n < 2047 on alkuluku, jos se on vahvasti pseudoalkuluku emäksissä a = 2;
luku n < 1 373 653 on alkuluku, jos se on vahvasti pseudoalkuluku kantojen a = 2, 3 suhteen;
luku n < 25 326 001 on alkuluku, jos se on vahvasti pseudoalkuluku emäksissä a = 2, 3, 5;
luku n < 3 215 031 751 on alkuluku, jos se on vahvasti pseudoalkuluku emäksissä a = 2, 3, 5, 7;
luku n < 2 152 302 898 747 on alkuluku, jos se on vahvasti pseudoalkuluku emäksissä a = 2, 3, 5, 7, 11;
luku n < 3 474 749 660 383 on alkuluku, jos se on vahvasti pseudoalkuluku emäksissä a = 2, 3, 5, 7, 11, 13;
luku n < 341 550 071 728 321 on alkuluku, jos se on vahvasti pseudoalkuluku emäksissä a = 2, 3, 5, 7, 11, 13, 17;
luku n < 3 825 123 056 546 413 051 on alkuluku, jos se on vahvasti pseudoalkuluku emäksissä a = 2, 3, 5, 7, 11, 13, 17, 19, 23;
luku n < 318665857834031151167461 on alkuluku, jos se on vahvasti pseudoalkuluku emäksissä a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37;
luku n < 3 317 044 064 679 887 385 961 981 on alkuluku, jos se on vahvasti pseudoalkuluku emäksissä a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 7,1, 1;
...
luku n < 1 543 267 864 443 420 616 877 677 640 751 301 on alkuluku, jos se on vahvasti pseudoalkuluku kaikissa alkulukumäärissä 2-61 mukaan lukien;
Luku on alkuluku, jos se on vahvasti pseudoalkuluku suhteessa kaikkiin alkulukuihin 2–71 mukaan lukien. $n<=10^{36}$

Ensimmäistä yhdistelmälukua , joka on vahvasti pseudoalkuluku kaikissa alkuluvuissa 71:een asti, ei ole vielä löydetty, mutta tiedetään, että . $n$ $n>10^{36}$

Toisin sanoen tiedetään (vuodesta 2016), että kaikki luvut, jotka ovat pienemmät kuin , jotka ovat vahvasti näennäisalkulukuja, ensimmäisten 20 emäksen mukaan (71 mukaan lukien) ovat myös alkulukuja . $10^{36}$

Näistä tiedoista näemme, että ensimmäiset luonnolliset luvut voidaan tarkistaa yksinkertaisuuden vuoksi ( lisäksi luotettavasti, koska tämä on jo todistettu ) käyttämällä kantalukua, jopa vähemmän kuin kaikissa yllä olevissa arvioissa. Tämä algoritmi on nopein numeroiden primaalisuuden tarkistamiseen. $10^{36}$

Käänteinen väite on seuraava - jos luku on alkuluku, niin se on vahvasti pseudo-alkuluku, yleensä kaikista syistä.

Algoritmista on myös versio, joka ei käytä laajennettua Riemannin hypoteesia. Tällä algoritmilla on eksponentiaalinen laskennallinen monimutkaisuus. Tässä tapauksessa funktion rooli on funktio . $f(n)$ $c\cdot n^{\tfrac {1}{1+4\sqrt e}} \approx c\cdot n^{0{,}133}$

Ominaisuudet

Determinismi : Testi on deterministinen, eli samalle n : lle tulos on aina sama. Tässä se eroaa esimerkiksi modifikaatiostaan, Miller-Rabinin testistä , joka on todennäköisyyspohjainen.
Polynomi : Testin suoritusaika riippuu korkeintaan polynomiaalisesti bitin pituudesta n , joka on suotuisa verrattuna raakavoimaan, Fermatin testiin tai Eratosthenesin seulaan . Testin suoritusnopeus on kuitenkin suuruusluokkaa hitaampi kuin Miller-Rabinin testissä .
Ehdollisuus : Algoritmin pääversiossa testi perustuu todentamattomaan laajennettuun Riemannin hypoteesiin , eli se on ehdollinen. Tämä testi eroaa Agrawal-Kayal-Saxena testistä , joka on täysin todistettu (ja myös deterministinen ja polynomi). Algoritmista on myös ehdoton versio, mutta se on paljon hitaampi kuin pääversio.

Aukioloajat

Siinä tapauksessa, että taulukon yläraja on annettu funktiolla , algoritmi tarkistaa deterministisesti luvun n ensisijaisuuden [4] :lle, mutta algoritmi perustuu yleistettyyn Riemannin hypoteesiin. Yksinkertaisesti sanottuna algoritmin monimutkaisuus kasvaa nopeammin kuin , (pseudosimplisiteetti tarkistettavien emästen lukumäärä), koska mitä suurempi kanta, sitä aikaa vievämpi sen analysointi. Syötetietojen koosta (mitta): tietueen pituus , tarkistettava numero , algoritmin monimutkaisuus riippuu seuraavista: , eli polynomin monimutkaisuus, 4. aste. $f(n)=2\cdot ln^{2}(n)$ $O(ln^{4}(n))$ $O(ln^{2}(n))$ $m$ $n$ $O(m^{4})$

Siinä tapauksessa, kun , pahimman tapauksen ajoaika on arvioitu [4] . Syötetietojen koosta: tietueen pituus , tarkistettava numero , algoritmin monimutkaisuus riippuu: , eli asteen eksponentiaalisesta monimutkaisuudesta 1/7. Tämä algoritmi on paljon monimutkaisempi: kaikki eksponentiaaliset algoritmit, joissa on riittävän suuri syöttödata, tulevat huomattavasti aikaa vievimmiksi kuin kaikki polynomialgoritmit. $f(n)=n^{0,133}$ $O(n^{1/7})$ $m$ $n$ $O(e^{m/7})$

Esimerkki algoritmin toteutuksesta

Esimerkki algoritmin toteutuksesta C#-ohjelmointikielellä (.NET Framework 3.5, 4.0).

Tämä on vain yksi esimerkeistä, ja maxChecked- muuttuja voidaan määritellä eri tavalla ja tarkastettavan luvun kaavalla (perinteinen Millerin testi) ja tarkoilla arvoilla luvuille, jotka ovat pienempiä kuin yllä kuvattu, ja yleensä mielivaltaisella tavalla, niin että algoritmin toteutus osoittautuu Miller-Rabiniksi. $2\cdot ln^{2}(n)$ $10^{36}$

public bool IsPrime_AlgMiller ( BigInteger checkingNum ) { // (jos on toisen luvun potenssi) if ( IsPowerOfNumber ( checkingNum )) return false ; BigInteger logN = uusi Isokokonaisluku ( BigInteger . Log ( checkingNum )); Isokokonaisluku loglogN = uusi isokokonaisluku ( BigKokonaisluku . Loki ( logN )); BigInteger maxChecked = logN * loglogN / ( uusi isokokonaisluku ( BigKonteger . Log ( 2 ))); // maxChecked: sai suurimman pohjan vahvan pseudoyksinkertaisuuden tarkistamiseen. Tämä on yksi esimerkki. BigInteger baseCurrent = uusi isokokonaisluku ( 2 ); bool isPrime = true ; while ( baseCurrent <= maxChecked ) { // (jos ei vahvasti pseudoprime tässä kantassa) if (! IsStrongPseudoPrime ( checkingNum , baseCurrent )) { // (niin luku ei ole alkuluku) isPrime = false ; tauko ; } baseCurrent = NextPrime ( baseCurrent ); } paluu isPrime ; } public bool IsStrongPseudoPrime ( Isokokonaisluku , perusvirta ) { Isokokonaisluku = checkingNum - 1 ; _ _ _ // (exp muuttuu, ja jäännöksen -1 tarkistaminen vastaa jäännöksen tarkistusta (checkingNum - 1)) BigInteger ost_1 = exp ; BigInteger res = BigInteger . ModPow ( baseCurrent , exp , checkingNum ); if ( res != 1 ) return false ; // (maatilatesti läpäissyt) while ( true ) { // (parillinen; ensimmäinen osuma on aina parillinen, sitten silmukka uudelleen parilliseen) exp = exp / 2 ; // (loppu -1 tulee aina tarkistaa) res = BigInteger . ModPow ( baseCurrent , exp , checkingNum ); if ( res == ost_1 ) return true ; // (tuli taas oudoksi - täytyy tarkistaa vielä 1) if (! exp . IsEven ) { res = BigInteger . ModPow ( baseCurrent , exp , checkingNum ); if ( res . IsOne ) return true ; tauko ; } } return false ; } julkinen BigInteger NextPrime ( BigInteger num ) { //... } julkinen 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) { palauttaa isokokonaisluku . SuurinYleinen jakaja ( BigInteger . ModPow ( 2 , n - 1 , n ) - 1 , n ) > 1 ; }

Jäljelle jää vain kaksi toimintoa -

1) NextPrime, joka vastaanottaa luvun ja palauttaa seuraavan alkuluvun, joka on optimaalinen vain pienten alkulukujen löytämiseen. Tämän toiminnon pitäisi olla vielä yksinkertaisempi ja nopeampi.

2) IsPowerOfNumber - hieman monimutkaisempi funktio, joka määrittää, onko välitetty luku toisen, alkuluvun potenssi. Meidän on löydettävä tämän toiminnon yksinkertaisin mahdollinen toteutus.

Myös,

3) Voit nopeuttaa algoritmin toteutusta suodattamalla ensin pois tapaukset, joissa luku on jaollinen mahdollisilla pienillä jakajilla, mutta usein esiintyvät jakajat: 2,3,5,7,11... ja vasta sitten suorita pää Tarkista Miller-algoritmin avulla.

Tässä tapauksessa Millerin algoritmin toteutus ehdotetussa esimerkissä on todennäköisesti nopein mielivaltaisille suurille luvuille. Ja itse algoritmi, kuten edellä on jo osoitettu, väittää olevansa nopein luotettava algoritmi primaalisuuden tarkistamiseen (jos yleistetty Riemannin hypoteesi pitää paikkansa).

Tämä algoritmin toteutus on testattu onnistuneesti ilman IsPowerOfNumber-funktiota.

Muistiinpanot

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

Kirjallisuus

Miller, Gary L. Riemannin hypoteesi ja primaalisuuden testit // Journal of Computer and System Sciences. - 1976. - T. 13 , no. 3 . — ISSN 0022-0000 . - doi : 10.1016/S0022-0000(76)80043-8 .
Ankeny NC Vähiten neliöllinen ei-jäännös // Annals of Mathematics. - 1952. - T. 55 .
H. Cohen , H. W. Lenstra, Jr. Primaliteettitestaus ja Jacobi-summat // Laskennan matematiikka. - 1984. - T. 42 , no. 165 .
Bach, Eric. Analyyttiset menetelmät lukuteoreettisten algoritmien analysoinnissa ja suunnittelussa . - Cambridge, MA: MIT Press, 1985. - 48 s. - ISBN 978-0-262-02219-4 .
Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa. - MTsNMO. - 2003. - ISBN 5-94057_103_4.

Lukuteoreettiset algoritmit
Yksinkertaisuustestit	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saksi Nightingale - Strassen
Alkulukujen löytäminen	Iterointi jakajien yli Eratosthenesin seula Atkinin seula Seula Sundarama
Faktorisointi	Iterointi jakajien yli Fermat menetelmä p −1 Pollardin menetelmä Pollardin ρ-algoritmi Lehmannin menetelmä Elliptisen käyrän menetelmä (Lenstran algoritmi) Dixonin algoritmi Neliömäinen seula
Diskreetti logaritmi	Gelfond-Shanks -algoritmi Polig-Hellman-algoritmi Pollardin ρ-menetelmä Pollardin kenguru-algoritmi Adlemanin algoritmi COS-algoritmi
GCD:n löytäminen	Eukleideen algoritmi Kehittynyt algoritmi Binäärinen algoritmi
Modulo-aritmetiikka	Montgomeryn algoritmi Kiinan jäännöslause
Lukujen kerto- ja jakolasku	Karatsuba-algoritmi Toom-Cook-algoritmi Schönhage-Strassen-algoritmi Fuhrer-algoritmi Harvey-van der Hoeven-algoritmi Burnickel-Ziegler-algoritmi
Neliöjuuren laskeminen	Tonelli-Shanks-algoritmi Berlekamp-Rabin-algoritmi