Test Millera-Rabina

Test Millera-Rabina – test pierwszości, czyli algorytm określający czy dana liczba jest pierwsza. Podobnie jak test Fermata i test Solovaya-Strassena jest testem probabilistycznym, wymagającym stosowania liczb losowych. Oryginalna wersja tego algorytmu (Millera) została zaprojektowana jako algorytm deterministyczny, jednak jej poprawność zależy od nieudowodnionej dotychczas uogólnionej hipotezy Riemanna. Michael O. Rabin zmodyfikował ten algorytm do postaci randomizacyjnej i dowiódł jego poprawności w tej postaci.

Algorytm można zapisać w następującej postaci:

Wejście: n > 1 : {\displaystyle n>1{:}} nieparzysta liczba naturalna do przetestowania;

k : {\displaystyle k{:}} parametr określający dokładność testu.

Wyjście: złożona, jeśli n {\displaystyle n} jest złożona, prawdopodobnie pierwsza, jeśli nie uda się stwierdzić złożoności;

wylicz maksymalną potęgę dwójki dzielącą n − 1 {\displaystyle n-1} i przedstaw n − 1 {\displaystyle n-1} jako 2 s ⋅ d ; {\displaystyle 2^{s}\cdot d;}

powtórzyć k {\displaystyle k} razy:

wybrać a {\displaystyle a} losowo ze zbioru { 1 , 2 , … , n − 1 } ; {\displaystyle \{1,2,\dots ,n-1\};}

jeśli a d ≢ 1 ( mod n ) {\displaystyle a^{d}\not \equiv 1({\bmod {n}})} i a 2 r d ≢ n − 1 ( mod n ) {\displaystyle a^{{2^{r}}d}\not \equiv n-1({\bmod {n}})} dla wszystkich r {\displaystyle r} ze zbioru Z s = { 0 , 1 , 2 , … , s − 1 } , {\displaystyle \mathbb {Z} _{s}=\{0,1,2,\dots ,s-1\},} zwróć wynik złożona.

zwróć wynik prawdopodobnie pierwsza.

Używając algorytmu szybkiego potęgowania można tę procedurę przeprowadzić w czasie O ( k ⋅ log 4 ⁡ n ) {\displaystyle \mathrm {O} (k\cdot \log ^{4}n)} , gdzie k {\displaystyle k} jest liczbą różnych testowanych wartości a . {\displaystyle a.}

Poprawność tego algorytmu opiera się na następujących dwóch twierdzeniach:

Załóżmy, że n {\displaystyle n} jest liczbą pierwszą oraz że a ∈ Z n ⋆ . {\displaystyle a\in \mathbb {Z} _{n}^{\star }.}

Niech dalej d = ( n − 1 ) / 2 s , {\displaystyle d=(n-1)/2^{s},} gdzie s = max { j : 2 j | ( n − 1 ) } . {\displaystyle s=\max\{j:2^{j}|(n-1)\}.} Wówczas albo a d ≡ 1 ( mod n ) , {\displaystyle a^{d}\equiv 1({\bmod {n}}),} albo istnieje r ∈ Z s , {\displaystyle r\in \mathbb {Z} _{s},} dla którego a 2 r ⋅ d ≡ − 1 ( mod n ) {\displaystyle a^{2^{r}\cdot d}\equiv -1({\bmod {n}})} ^[1].

Liczbę a ∈ Z n ⋆ , {\displaystyle a\in \mathbb {Z} _{n}^{\star },} która nie spełnia warunków powyższego twierdzenia nazywa się świadkiem złożoności liczby n . {\displaystyle n.}

Jeśli n ⩾ 3 {\displaystyle n\geqslant 3} jest nieparzystą liczbą złożoną, to w zbiorze Z n ⋆ {\displaystyle \mathbb {Z} _{n}^{\star }} jest co najwyżej ( n − 1 ) / 4 {\displaystyle (n-1)/4} liczb niebędących świadkami jej złożoności^[1].

Należy określić, czy liczba n = 221 {\displaystyle n=221} jest pierwsza.

Zapisując n − 1 = 220 {\displaystyle n-1=220} w postaci 2 2 ⋅ 55 , {\displaystyle 2^{2}\cdot 55,} otrzymuje się s = 2 {\displaystyle s=2} oraz d = 55. {\displaystyle d=55.} Następnie trzeba wybrać losowo liczbę a < n . {\displaystyle a<n.} Jeśli wylosowaną liczbą jest a = 174 , {\displaystyle a=174,} wtedy dla r {\displaystyle r} ze zbioru { 0 , 1 } : {\displaystyle \{0,1\}{:}}

• a 2 0 ⋅ d mod n = 174 55 mod 2 21 = 47 ≠ 1 , {\displaystyle a^{2{^{0}}\cdot d}{\bmod {n}}=174^{55}{\bmod {2}}21=47\neq 1,} i ≠ n − 1 , {\displaystyle \neq n-1,} więc nierównoważne − 1 mod n . {\displaystyle -1{\bmod {n}}.}
• a 2 1 ⋅ d mod n = 174 110 mod 2 21 = 220 = n − 1. {\displaystyle a^{2{^{1}}\cdot d}{\bmod {n}}=174^{110}{\bmod {2}}21=220=n-1.}

Ponieważ 220 ≡ − 1 mod n , {\displaystyle 220\equiv -1{\bmod {n}},} to albo liczba 221 jest pierwsza, albo 174 jest fałszywym świadkiem dla 221. W tym przypadku następuje losowanie kolejnej wartość a , {\displaystyle a,} tym razem a = 137 : {\displaystyle a=137{:}}

• a 2 0 ⋅ d mod n = 137 55 mod 2 21 = 188 ≠ 1 {\displaystyle a^{2{^{0}}\cdot d}{\bmod {n}}=137^{55}{\bmod {2}}21=188\neq 1} i ≠ n − 1 , {\displaystyle \neq n-1,} więc nierównoważne − 1 mod n . {\displaystyle -1{\bmod {n}}.}
• a 2 1 ⋅ d mod n = 137 110 mod 2 21 = 205 ≠ n − 1. {\displaystyle a^{2{^{1}}\cdot d}{\bmod {n}}=137^{110}{\bmod {2}}21=205\neq n-1.}

A zatem 137 jest świadkiem złożoności 221, a 174 jest faktycznie fałszywym świadkiem. W tym przypadku test pozwala także dokonać rozkładu liczby:

NWD(137−1, 221) = 17

221 / 17 = 13

zatem 221 = 17 · 13

Można pokazać, że dla dowolnej złożonej nieparzystej liczby naturalnej n {\displaystyle n} co najmniej 3/4 możliwych wartości a {\displaystyle a} jest dobrymi świadkami złożoności tej liczby. Jeśli zatem przeprowadzamy k {\displaystyle k} losowych prób, prawdopodobieństwo, że określimy liczbę złożoną jako pierwszą wynosi co najwyżej 4 − k . {\displaystyle 4^{-k}.}

Istnieją deterministyczne wersje tego testu, jednak w ogólności są one znacznie wolniejsze i głównie dlatego nie mają zastosowania praktycznego. Dla małych n {\displaystyle n} udowodniono, że można test przeprowadzić znacznie szybciej^[2][3][4]:

• jeśli n < 4   759   123   141 , {\displaystyle n<4\ 759\ 123\ 141,} wystarczy sprawdzić a = 2 , 7   i   61 ; {\displaystyle a=2,7\ \mathrm {i} \ 61;}
• jeśli n < 341   550   071   728   321 , {\displaystyle n<341\ 550\ 071\ 728\ 321,} wystarczy sprawdzić a = 2 , 3 , 5 , 7 , 11 , 13   i   17. {\displaystyle a=2,3,5,7,11,13\ \mathrm {i} \ 17.}

(inne tego typu kryteria opisano np. w The Prime Pages i SPRP bases)

Daje to bardzo szybki deterministyczny test pierwszości dla liczb z tego zakresu, bez żadnych dodatkowych założeń. Udowodniono jednak, że żaden skończony zbiór a {\displaystyle a} nie wystarcza do testowania wszystkich liczb złożonych.

• Eric W.E.W. Weisstein Eric W.E.W., Rabin-Miller Strong Pseudoprime Test, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).