Test pierwszości Millera-Rabina - Miller–Rabin primality test

Test Millera-Rabina lub test pierwszości Rabina Millera jest probabilistycznych testów pierwszości : AN algorytm , który określa, czy dana liczba jest prawdopodobnie pierwsza podobny do testu pierwszości Fermat i test pierwszości solovaya-strassena .

Ma to znaczenie historyczne w poszukiwaniu wielomianowego deterministycznego testu pierwszości. Jej wariant probabilistyczny pozostaje szeroko stosowany w praktyce, jako jeden z najprostszych i najszybszych znanych testów.

Gary L. Miller odkrył test w 1976 roku; Wersja testu Millera jest deterministyczna , ale jej poprawność opiera się na niesprawdzonej, rozszerzonej hipotezie Riemanna . Michael O. Rabin zmodyfikował go, aby uzyskać bezwarunkowy algorytm probabilistyczny w 1980 roku.

Koncepcje matematyczne

Podobnie jak w przypadku testów Fermata i Solovay-Strassena, test pierwszości Millera-Rabina sprawdza, czy określona właściwość, o której wiadomo, że zachodzi dla wartości pierwszych, jest aktualna dla badanej liczby.

Silne prawdopodobne liczby pierwsze

Właściwość jest następująca. Dla danej nieparzystej liczby całkowitej n > 2 zapiszmy n jako 2 ^s ⋅ d + 1 gdzie s i d są liczbami całkowitymi dodatnimi, a d jest nieparzyste. Rozważmy liczbę całkowitą  a , nazywaną podstawą , taką że 0 < a < n . Wtedy mówi się, że n jest silną prawdopodobną liczbą pierwszą do oparcia a, jeśli zachodzi jedna z tych relacji kongruencji :

• ${\ Displaystyle a ^ {d} \ równoważ 1 {\ pmod {n}}}$;
• ${\ Displaystyle a ^ {2 ^ {r} \ cdot d} \ równoważnik -1 {\ pmod {n}}}$ dla niektórych 0 ≤ r < s .

Ideą tego testu jest to, że gdy n jest nieparzystą liczbą pierwszą, przechodzi test z dwóch powodów:

• przez małego twierdzenia Fermata , (ten sam definiuje właściwość słabsze pojęcie prawdopodobnej sile na podstawę , na której opiera się test Fermat);${\ Displaystyle a ^ {n-1} \ równoważne 1 {\ pmod {n}}}$
• jedyne pierwiastki kwadratowe z 1 modulo n to 1 i -1.

Stąd, w przeciwieństwie do , jeśli n nie jest silną prawdopodobną liczbą pierwszą dla podstawy a , to n jest zdecydowanie złożona, a a jest nazywane świadkiem złożoności n (czasami myląco nazywanym silnym świadkiem ).

Jednak ta własność nie jest dokładną charakterystyką liczb pierwszych. Jeśli n jest złożone, to jednak może być silną prawdopodobną liczbą pierwszą opartą na a , w którym to przypadku nazywa się ją silną pseudopierwszą , a a jest silnym kłamcą .

Wybór baz

Na szczęście żadna liczba złożona nie jest silnym pseudopierwszym dla wszystkich zasad jednocześnie. Nie jest jednak znany prosty sposób odnalezienia świadka. Naiwnym rozwiązaniem jest wypróbowanie wszystkich możliwych zasad, co daje nieefektywny algorytm deterministyczny. Test Millera jest bardziej wydajnym wariantem tego (patrz sekcja Test Millera poniżej ).

Innym rozwiązaniem jest losowy wybór bazy. Daje to szybki test probabilistyczny . Gdy n jest złożone, większość zasad jest świadkami, więc test wykryje n jako złożoną z dość wysokim prawdopodobieństwem (patrz sekcja Dokładność poniżej ). Możemy szybko zredukować prawdopodobieństwo wystąpienia fałszywie pozytywnego wyniku do dowolnie małego współczynnika, łącząc wynik tylu niezależnie wybranych zasad, ile jest konieczne do osiągnięcia tego współczynnika. To jest test Millera-Rabina. Liczba zasad do wypróbowania nie zależy od n . Wydaje się, że przy próbowaniu wielu zasad zwroty maleją, ponieważ jeśli n jest liczbą pseudopierwszą dla jakiejś zasady, to wydaje się bardziej prawdopodobne, że jest liczbą pseudopierwszą dla innej zasady.

Do testowania arbitralnie dużych n niezbędne jest losowe wybieranie baz, ponieważ nie znamy rozmieszczenia świadków i silnych kłamców wśród liczb 1, 2, …, n −1 .

Jednak wstępnie dobrany zestaw kilku małych baz gwarantuje identyfikację wszystkich kompozytów aż do wstępnie obliczonego maksimum. To maksimum jest na ogół dość duże w porównaniu do zasad. Daje to bardzo szybkie testy deterministyczne dla wystarczająco małych n (patrz sekcja Testowanie na małych zestawach zasad poniżej ).

Dowody

Oto dowód, że gdy n jest nieparzystą liczbą pierwszą, jedyne pierwiastki kwadratowe z 1 modulo n to 1 i -1.

Oto dowód, że jeśli n jest nieparzystą liczbą pierwszą, to jest to silna prawdopodobna liczba pierwsza oparta na a .

Przykład

Załóżmy, że chcemy ustalić, czy n  = 221 jest liczbą pierwszą. Zapisujemy n −1 jako 2 ² ·55, więc mamy s  = 2 i d  = 55. Losowo wybieramy liczbę a taką, że 1 <  a  <  n - 1, powiedzmy a = 174. Przystępujemy do obliczenia:

• a ^{2 0 · d} mod n = 174 ⁵⁵ mod 221 = 47 ≠ 1, n − 1
• a ^{2 1 · d} mod n = 174 ¹¹⁰ mod 221 = 220 = n − 1.

Ponieważ 220 ≡ -1 mod n , albo 221 jest liczbą pierwszą, albo 174 jest silnym kłamcą dla 221. Próbujemy innego losowego a , tym razem wybierając a = 137:

• a ^{2 0 · d} mod n = 137 ⁵⁵ mod 221 = 188 ≠ 1, n − 1
• a ^{2 1 · d} mod n = 137 ¹¹⁰ mod 221 = 205 ≠ n − 1.

Stąd 137 jest świadkiem złożoności 221, a 174 był w rzeczywistości silnym kłamcą. Zauważ, że nie mówi nam to nic o dzielnikach 221 (czyli 13 i 17). Jednak przykład z 341 w dalszej części pokazuje, jak te obliczenia mogą czasami dawać współczynnik n .

Test Millera-Rabina

Algorytm można zapisać w pseudokodzie w następujący sposób. Parametr k określa dokładność testu. Im większa liczba rund, tym dokładniejszy wynik.

Input #1: n > 3, an odd integer to be tested for primality
Input #2: k, the number of rounds of testing to perform
Output: “composite” if n is found to be composite, “probably prime” otherwise

write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1)
WitnessLoop: repeat k times:
    pick a random integer a in the range [2, n − 2]
    x ← ad mod n
    if x = 1 or x = n − 1 then
        continue WitnessLoop
    repeat r − 1 times:
        x ← x2 mod n
        if x = n − 1 then
            continue WitnessLoop
    return “composite”
return “probably prime”

Złożoność

Stosując powtarzane do kwadratu , czas działania tego algorytmu wynosi O ( k  log ³ n ) , gdzie n to liczba testowana pod kątem pierwszości, a k to liczba wykonanych rund; jest to zatem wydajny algorytm wielomianowy. Mnożenie oparte na FFT może skrócić czas działania do 0 ( k log ² n log log n log log log n ) = Õ ( k  log ² n ) .

Precyzja

Błąd popełniony w teście pierwszości jest mierzony prawdopodobieństwem, że liczba złożona jest uznana za prawdopodobnie pierwszą. Im więcej zasad A są próbował, tym lepsza dokładność testu. Można wykazać, że jeśli n jest złożone, to co najwyżej 1 ⁄ 4 zasad a są silnymi kłamcami dla n . W konsekwencji, jeśli n jest liczbą złożoną następnie uruchomiony k powtórzeń testu Millera-Rabina uzna n prawdopodobnie podstawowym z prawdopodobieństwem co najwyżej 4 ^{- k} .

Jest to ulepszenie w stosunku do testu Solovay-Strassena , którego granica najgorszego przypadku błędu wynosi 2 ^{− k} . Ponadto, test Millera Rabina ściśle silniejsze niż test Solovay-Strassen w tym sensie, że dla każdego kompozytu N , zestaw silnych kłamców dla n jest podzbiorem zbioru kłamców Eulera do n , i wiele N The podzbiór jest właściwy.

Ponadto dla dużych wartości n prawdopodobieństwo, że liczba złożona zostanie zadeklarowana jako prawdopodobnie pierwsza, jest często znacznie mniejsze niż 4 ^{− k} . Na przykład dla większości liczb n prawdopodobieństwo to jest ograniczone przez 8 ^{− k} ; proporcja liczb n, które unieważniają tę górną granicę, znika, gdy rozważamy większe wartości n . Stąd średni przypadek ma znacznie lepszą dokładność niż 4 ^{− k} , fakt, który można wykorzystać do generowania prawdopodobnych liczb pierwszych (patrz poniżej ). Nie należy jednak polegać na takich ulepszonych granicach błędów w celu weryfikacji liczb pierwszych, których rozkład prawdopodobieństwa nie jest kontrolowany, ponieważ przeciwnik kryptograficzny może wysłać starannie wybraną liczbę pseudopierwszą w celu pokonania testu pierwszości. W takich kontekstach można polegać tylko na najgorszym przypadku błędu związanego z 4 ^{− k} .

Powyższa miara błędu jest prawdopodobieństwem, że liczba złożona zostanie zadeklarowana jako silna prawdopodobna liczba pierwsza po k rundach testowania; w matematycznych słowach jest to prawdopodobieństwo warunkowe, gdzie P jest zdarzeniem , w którym testowana liczba jest pierwsza, a MR _k jest zdarzeniem, w którym przechodzi test Millera-Rabina z k rund. Zamiast tego często interesuje nas odwrotne prawdopodobieństwo warunkowe : prawdopodobieństwo, że liczba, która została zadeklarowana jako silna prawdopodobna liczba pierwsza, jest w rzeczywistości złożona. Te dwa prawdopodobieństwa są powiązane prawem Bayesa : ${\ Displaystyle \ Pr (M \! R_ {k} \ mid \ l nie P)}$${\ Displaystyle \ Pr (\ nie P \ mid M \! R_ {k})}$

${\ Displaystyle \ Pr (\ l nie P \ mid M \! R_ {k}) = {\ Frac {\ Pr (\ nie P \ ziemia M \! R_ {k})} {\ pr (\ nie P \ ziemia M\!R_{k})+\Pr(P\land M\!R_{k})}}={\frac {1}{1+{\frac {\Pr(M\!R_{k}\ mid P)}{\Pr(M\!R_{k}\mid \lnot P)}}\cdot {\frac {\Pr(P)}{\Pr(\lnot P)}}}}={\ frac {1}{1+{\frac {1}{\Pr(M\!R_{k}\mid \lnot P)}}\cdot {\frac {\Pr(P)}{1-\Pr( P)}}}}}$

W ostatnim równaniu uprościliśmy wyrażenie, używając faktu, że wszystkie liczby pierwsze są poprawnie zgłaszane jako silne prawdopodobne liczby pierwsze (test nie ma wyników fałszywie ujemnych ). Upuszczając lewą część mianownika , wyprowadzamy prostą górną granicę:

${\ Displaystyle \ Pr (\ l nie P \ mid M \! R_ {k}) < \ Pr (M \! R_ {k} \ mid \ l nie P) \ cdot \ lewo ({\ tfrac {1} {\ Pr (P)}}-1\prawo)}$

Stąd to warunkowe prawdopodobieństwo jest związane nie tylko z omówioną powyżej miarą błędu — która jest ograniczona przez 4 ^{− k}  — ale także z rozkładem prawdopodobieństwa liczby wejściowej. W ogólnym przypadku, jak wspomniano wcześniej, dystrybucja ta jest kontrolowana przez przeciwnika kryptograficznego, a więc nieznanego, więc nie możemy wiele wydedukować na temat . Jednak w przypadku, gdy używamy testu Millera-Rabina do generowania liczb pierwszych (patrz niżej ), rozkład jest wybierany przez sam generator, więc możemy wykorzystać ten wynik. ${\ Displaystyle \ Pr (\ nie P \ mid M \! R_ {k})}$

Warianty deterministyczne

Test Millera

Algorytm Millera-Rabina mogą być deterministyczny próbując wszelkich możliwych A poniżej pewnej granicy. Przyjęcie n jako limitu sugerowałoby O( n ) prób, stąd czas działania byłby wykładniczy w odniesieniu do wielkości log n danych wejściowych. Aby poprawić czas działania, wyzwaniem jest obniżenie limitu tak bardzo, jak to możliwe, przy jednoczesnym zachowaniu wiarygodności testu.

Jeżeli testowana liczba n jest złożona, to silni kłamcy a względnie pierwsze do n są zawarte w odpowiedniej podgrupie grupy ( Z / n Z )*, co oznacza, że ​​jeśli testujemy wszystkie a ze zbioru, który generuje ( Z / n Z ) )*, jeden z nich musi leżeć poza wspomnianą podgrupą, a więc musi być świadkiem złożoności n . Zakładając, że prawdziwości uogólnionego Riemanna hipotezy (GRH), wiadomo, że grupa ta jest generowane przez jej elementy mniejsze niż O (( ln n ) ² ) , które zostało już stwierdzone przez Millera. Stała zaangażowana w notację Big O została zredukowana do 2 przez Erica Bacha . Prowadzi to do następującego deterministycznego algorytmu testowania pierwszości, znanego jako test Millera :

Input: n > 1, an odd integer to be tested for primality
Output: “composite” if n is composite, “prime” otherwise

write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1)
WitnessLoop: for all a in the range [2, min(n−2, ⌊2(ln n)2⌋)]:
    x ← ad mod n
    if x = 1 or x = n − 1 then
        continue WitnessLoop
    repeat r − 1 times:
        x ← x2 mod n
        if x = n − 1 then
            continue WitnessLoop
    return “composite”
return “prime”

Pełna moc uogólnionej hipotezy Riemanna nie jest potrzebna do zapewnienia poprawności testu: ponieważ mamy do czynienia z podgrupami o indeksie parzystym , wystarczy założyć słuszność GRH dla kwadratowych znaków Dirichleta .

Czas działania algorytmu to, w notacji soft-O , Õ((log n ) ⁴ ) (przy użyciu mnożenia opartego na FFT).

Test Millera nie jest stosowany w praktyce. Dla większości celów właściwe użycie probabilistycznego testu Millera–Rabina lub testu pierwszości Baillie–PSW daje wystarczającą pewność przy znacznie szybszym biegu. Jest również wolniejszy w praktyce niż powszechnie stosowane metody dowodowe, takie jak APR-CL i ECPP, które dają wyniki, które nie opierają się na niesprawdzonych założeniach. Dla celów teoretycznych wymagających deterministycznego algorytmu wielomianowego czasu, został on zastąpiony przez test pierwszości AKS , który również nie opiera się na niesprawdzonych założeniach.

Testowanie na małych zestawach zasad

Gdy liczba n do przetestowania jest mała, próbowanie wszystkich a < 2(ln n ) ² nie jest konieczne, ponieważ wiadomo, że wystarczą mniejsze zestawy potencjalnych świadków. Stwierdzili to na przykład Pomerance, Selfridge, Wagstaff i Jaeschke

• jeśli n < 2047, wystarczy przetestować a = 2;
• jeśli n < 1 373 653, wystarczy przetestować a = 2 i 3;
• jeśli n < 9 080 191, wystarczy przetestować a = 31 i 73;
• jeśli n < 25 326 001, wystarczy przetestować a = 2, 3 i 5;
• jeśli n < 3 215 031 751, wystarczy przetestować a = 2, 3, 5 i 7;
• jeśli n < 4 759 123 141, wystarczy przetestować a = 2, 7 i 61;
• jeśli n < 1 122 004 669 633, wystarczy przetestować a = 2, 13, 23 i 1662803;
• jeśli n < 2 152 302 898 747, wystarczy przetestować a = 2, 3, 5, 7 i 11;
• jeśli n < 3 474 749 660 383, wystarczy przetestować a = 2, 3, 5, 7, 11 i 13;
• jeśli n < 341,550,071,728,321, wystarczy przetestować a = 2, 3, 5, 7, 11, 13 i 17.

Korzystając z pracy Feitsmy i Galwaya wyliczenia wszystkich liczb pseudopierwszych o podstawie 2 w 2010 r., zostało to rozszerzone (patrz OEIS :  A014233 ), przy czym pierwszy wynik pokazano później przy użyciu różnych metod w Jiangu i Dengu :

• jeśli n < 3 825 123 056 546 413 051, wystarczy przetestować a = 2, 3, 5, 7, 11, 13, 17, 19 i 23.
• jeśli n < 18 446 744 073 709 551 616 = 2 ⁶⁴ , wystarczy przetestować a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 i 37.

Sorenson i Webster weryfikują powyższe i obliczają dokładne wyniki dla tych wyników większych niż 64-bitowe:

• jeśli n < 318 665 857 834 031 151 167 461 wystarczy przetestować a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 i 37.
• jeśli n < 3 317 044 064 679 887 385 961 981, wystarczy przetestować a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 i 41.

Istnieją inne kryteria tego rodzaju, często bardziej efektywne (wymagana mniejsza liczba zasad) niż te przedstawione powyżej. Dają bardzo szybkie deterministyczne testy pierwszości dla liczb w odpowiednim zakresie, bez żadnych założeń.

Istnieje mała lista potencjalnych świadków dla każdego możliwego rozmiaru danych wejściowych (co najwyżej b wartości dla liczb b- bitowych). Jednak żaden skończony zbiór zasad nie jest wystarczający dla wszystkich liczb złożonych. Alford, Granville i Pomerance wykazali, że istnieje nieskończenie wiele liczb złożonych n, których najmniejszym świadectwem ^{złożoności} jest co najmniej (ln n ) ^{1/(3ln ln ln n )} . Twierdzą również heurystycznie, że najmniejsza liczba w taka, że ​​każda liczba złożona poniżej n ma świadectwo złożoności mniejsze niż w powinno być rzędu Θ (log n log log n ).

Warianty znajdowania czynników

Wstawiając obliczenia największego wspólnego dzielnika do powyższego algorytmu, możemy czasami uzyskać współczynnik n zamiast po prostu określić, że n jest złożone. Dzieje się tak na przykład, gdy n jest prawdopodobną pierwszą bazą a, ale nie silną prawdopodobną pierwszą bazą a . Możemy wykryć ten przypadek w algorytmie, porównując x w wewnętrznej pętli nie tylko do -1, ale także do 1.

Jeżeli w pewnej iteracji 1 ≤ i < r pętli wewnętrznej algorytm odkrywa, że ​​wartość a ^{d ·2 i} mod n zmiennej x jest równa 1, to wiedząc, że poprzednia wartość x ₀ = a ^{d ·2} Sprawdzono, czy ^{s- 1} zmiennej x różni się od ±1, możemy wywnioskować, że x ₀ jest pierwiastkiem kwadratowym z 1, który nie jest ani 1, ani -1. Ponieważ nie jest to możliwe, gdy n jest liczbą pierwszą, oznacza to, że n jest złożone. Ponadto:

• ponieważ x ₀ ² ≡ 1 (mod n ) , wiemy, że n dzieli x ₀ ² − 1 = ( x ₀ − 1)( x ₀ + 1) ;
• ponieważ x ₀ ≢ ±1 (mod n ) , wiemy, że n nie dzieli x ₀ − 1 ani x ₀ + 1 .

Z tego wnioskujemy, że A = GCD( x ₀ − 1, n ) i B = GCD( x ₀ + 1, n ) są nietrywialnymi (niekoniecznie pierwszymi) czynnikami n (w rzeczywistości, ponieważ n jest nieparzyste, te czynniki są względnie pierwsze i n = A · B ). W związku z tym, jeśli celem jest faktoring, te obliczenia GCD można wprowadzić do algorytmu przy niewielkim dodatkowym koszcie obliczeniowym. Prowadzi to do następującego pseudokodu, w którym dodany lub zmieniony kod jest podświetlony:

Input #1: n > 3, an odd integer to be tested for primality
Input #2: k, the number of rounds of testing to perform
Output: (“multiple of”, m) if a non‐trivial factor m of n is found,
        “composite” if n is otherwise found to be composite,
        “probably prime” otherwise

write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1)
WitnessLoop: repeat k times:
    pick a random integer a in the range [2, n − 2]
    x ← ad mod n
    if x = 1 or x = n − 1 then
        continue WitnessLoop
    repeat r − 1 times:
        y ← x2 mod n
        if y = 1:
            return (“multiple of”, GCD(x − 1, n))
        x ← y
        if x = n − 1 then
            continue WitnessLoop
    return “composite”
return “probably prime”

Algorytm ten nie daje algorytmu probabilistycznego faktoryzacji , ponieważ jest on w stanie znaleźć czynniki tylko dla liczb n, które są pseudopierwsze przy podstawie a (innymi słowy, dla liczb n takich, że a ^{n -1} ≡ 1 mod n ). W przypadku innych liczb algorytm zwraca tylko „ złożony ” bez dalszych informacji.

Rozważmy na przykład n = 341 i a = 2. Mamy n − 1 = 85,4. Wtedy 2 ⁸⁵ mod 341 = 32. i 32 ² mod 341 = 1. To mówi nam, że n jest pseudopierwszą bazą 2, ale nie silną pseudopierwszą bazą 2. Obliczając GCD na tym etapie, znajdujemy współczynnik 341: NWD(32 − 1, 341) = 31. Rzeczywiście, 341 = 11,31 .

Aby częściej znajdować czynniki, te same pomysły można również zastosować do pierwiastków kwadratowych z -1 (lub dowolnej innej liczby). Strategia ta może być realizowana poprzez wykorzystanie wiedzy z poprzednich rund testu Millera–Rabina. W tych rundach mogliśmy zidentyfikować pierwiastek kwadratowy modulo n z -1, powiedzmy R . Wtedy, gdy x ² mod n = n −1 , możemy porównać wartość x z R : jeśli x nie jest ani R ani n − R , to GCD( x − R , n ) i GCD( x + R , n ) są nietrywialnymi czynnikami n .

Generowanie prawdopodobnych liczb pierwszych

Test Millera-Rabina może być użyty do wygenerowania silnych prawdopodobnych liczb pierwszych, po prostu losując liczby całkowite, dopóki jeden z nich nie przejdzie testu. Ten algorytm kończy się prawie na pewno (ponieważ w każdej iteracji jest szansa na wylosowanie liczby pierwszej). Pseudokod do generowania b - bitowych silnych prawdopodobnych liczb pierwszych (z ustawionym najbardziej znaczącym bitem) wygląda następująco:

Input #1: b, the number of bits of the result
Input #2: k, the number of rounds of testing to perform
Output: a strong probable prime n

while True:
    pick a random odd integer n in the range [2b−1, 2b−1]
    if the Miller–Rabin test with inputs n and k returns “probably prime” then
        return n

Złożoność

Oczywiście najgorszy czas działania jest nieskończony, ponieważ zewnętrzna pętla może nigdy się nie zakończyć, ale dzieje się to z prawdopodobieństwem zerowym. Zgodnie z rozkładu geometrycznego The oczekuje ilość opiera się (ponowne oznaczenia z wcześniej ). ${\ Displaystyle {\ tfrac {1} {\ Pr (M \! R_ {k})}}}$

Ponieważ każda liczba pierwsza przechodzi test, prawdopodobieństwo bycia pierwszą daje zgrubne dolne ograniczenie prawdopodobieństwa zdania testu. Jeśli narysujemy liczby nieparzyste równomiernie w przedziale [2 ^{b −1} , 2 ^b −1], to otrzymujemy:

${\ Displaystyle \ Pr (M \! R_ {k})> \ Pr (P) = {\ Frac {\ pi \ lewo (2 ^ {b} \ po prawej) - \ pi \ po lewej (2 ^ {b-1 }\prawo)}{2^{b-2}}}}$

gdzie π jest funkcją zliczania liczb pierwszych . Używając asymptotycznego rozwinięcia π (rozszerzenie twierdzenia o liczbach pierwszych ), możemy przybliżyć to prawdopodobieństwo, gdy b rośnie w kierunku nieskończoności. Znaleźliśmy:

${\ Displaystyle \ Pr (P) = {\ tfrac {2} {\ ln 2}} b ^ {-1} + {\ mathcal {O}} \ lewo (b ^ {-3} \ prawej)}$

${\ Displaystyle {\ tfrac {1} {\ Pr (P)}} = {\ tfrac {\ ln 2} {2}} b + {\ mathcal {O}} \ po lewej (b ^ {-1} \ po prawej) }$

Dlatego możemy oczekiwać, że generator wykona nie więcej testów Millera-Rabina niż liczbę proporcjonalną do b . Biorąc pod uwagę najgorszy przypadek złożoności każdego testu Millera-Rabina (patrz wcześniej ), oczekiwany czas działania generatora z wejściami b i k jest następnie ograniczony przez O( k b ⁴ ) (lub Õ( k b ³ ) za pomocą mnożenie na podstawie FFT).

Precyzja

Miarą błędu tego generatora jest prawdopodobieństwo, że wyprowadza liczbę złożoną.

Korzystając z relacji między prawdopodobieństwami warunkowymi (pokazanymi we wcześniejszej sekcji ) a asymptotycznym zachowaniem (pokazanym tuż wcześniej), tej mierze błędu można nadać zgrubną górną granicę: ${\ Displaystyle \ Pr (P)}$

${\ Displaystyle \ Pr (\ l nie P \ mid M \! R_ {k}) < \ Pr (M \! R_ {k} \ mid \ l nie P) \ cdot \ lewo ({\ tfrac {1} {\ Pr (P)}}-1\right)\leq 4^{-k}\cdot \left({\tfrac {\ln 2}{2}}b-1+{\mathcal {O}}\left(b ^{-1}\prawo)\prawo)}$

Stąd, dla wystarczająco dużego b , ta miara błędu jest mniejsza niż . Istnieją jednak znacznie lepsze granice. ${\ Displaystyle {\ tfrac {\ ln 2} {2}} \ cdot b \ cdot 4 ^ {-k}}$

Korzystając z faktu, że sam test Millera-Rabina często ma błąd graniczny znacznie mniejszy niż 4 ^{− k} (patrz wcześniej ), Damgård , Landrock i Pomerance wyprowadzili kilka granic błędów dla generatora, z różnymi klasami parametrów b i k . Te granice błędów pozwalają wdrażającemu wybrać rozsądne k dla pożądanej dokładności.

Jedną z tych granic błędu jest 4 ^{− k} , która obowiązuje dla wszystkich b ≥ 2 (autorzy pokazali to tylko dla b ≥ 51, podczas gdy Ronald Burthe Jr. uzupełnił dowód pozostałymi wartościami 2 ≤ b ≤ 50). Znowu to proste ograniczenie można poprawić dla dużych wartości b . Na przykład innym wiązaniem wyprowadzonym przez tych samych autorów jest:

${\ Displaystyle \ lewo ({\ tfrac {1} {7}} b ^ {15/4} 2 ^ {-b/2} \ prawej) \ cdot 4 ^ {-k}}$

która obowiązuje dla wszystkich b ≥ 21 i k ≥ b ⁄ 4 . Ta granica jest mniejsza niż 4 ^{− k,} gdy b ≥ 32.

Uwagi

Bibliografia

Zewnętrzne linki

• Weisstein, Eric W. "Test Rabina-Millera na silne Pseudoprime" . MatematykaŚwiat .
• Interaktywna implementacja online wariantu deterministycznego (krok po kroku przez algorytm)
• Aplet (niemiecki)
• Test pierwszości Millera–Rabina w C#
• Test pierwszości Millera–Rabina w JavaScript z wykorzystaniem arytmetyki arbitralnej precyzji