Tekst źródłowy strony Test Millera-Rabina

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

== Algorytm i czas działania ==
Algorytm można zapisać w następującej postaci:

'''Wejście:''' <math>n > 1{:}</math> nieparzysta [[Liczby naturalne|liczba naturalna]] do przetestowania;
: <math>k{:}</math> parametr określający dokładność testu.

'''Wyjście:''' <u>złożona</u>, jeśli <math>n</math> jest złożona, <u>prawdopodobnie pierwsza</u>, jeśli nie uda się stwierdzić złożoności;
: wylicz maksymalną [[potęga dwójki|potęgę dwójki]] dzielącą <math>n-1</math> i przedstaw <math>n-1</math> jako <math>2^s \cdot d;</math>
: powtórzyć <math>k</math> razy:
:: wybrać <math>a</math> losowo ze zbioru <math>\{1,2,\dots, n - 1\};</math>
:: jeśli <math>a^d \not\equiv 1 (\bmod n)</math> i <math>a^{{2^r}d} \not\equiv n-1 (\bmod n)</math> dla wszystkich <math>r</math> ze zbioru <math>\mathbb Z_s=\{0,1,2,\dots, s - 1\},</math> zwróć wynik <u>złożona</u>.
: zwróć wynik <u>prawdopodobnie pierwsza</u>.

Używając [[Algorytm szybkiego potęgowania|algorytmu szybkiego potęgowania]] można tę procedurę przeprowadzić w czasie [[Asymptotyczne tempo wzrostu|<math>\Omicron(k \cdot \log^4 n)</math>]], gdzie <math>k</math> jest liczbą różnych testowanych wartości <math>a.</math>

== Dowód poprawności ==
Poprawność tego algorytmu opiera się na następujących dwóch twierdzeniach:

=== Twierdzenie 1 ===
Załóżmy, że <math>n</math> jest liczbą pierwszą oraz że <math>a\in\mathbb{Z}_n^\star.</math>

Niech dalej <math>d=(n-1)/2^s,</math> gdzie <math>s=\max\{j:2^j|(n-1)\}.</math> Wówczas albo <math>a^d\equiv 1 (\bmod n),</math> albo istnieje <math>r\in\mathbb Z_s,</math> dla którego <math>a^{2^r\cdot d}\equiv -1 (\bmod n)</math><ref name=":0">{{Cytuj |autor = Johannes A. Buchmann, Wojciech Guzicki |tytuł = Wprowadzenie do kryptografii |data = 2006 |data dostępu = 2024-06-14 |isbn = 978-83-01-14868-3 |opis = Informatyka - Zastosowania |miejsce = Warszawa |wydawca = Wydawnictwo Naukowe PWN |s = 116-117 |język = pl}}</ref>.

Liczbę <math>a\in\mathbb Z_n^\star,</math> która '''nie''' spełnia warunków powyższego twierdzenia nazywa się ''świadkiem złożoności'' liczby <math>n.</math>

=== Twierdzenie 2 ===
Jeśli <math>n\geqslant3</math> jest nieparzystą [[Liczby złożone|liczbą złożoną]], to w zbiorze <math>\mathbb Z_n^\star</math> jest co najwyżej <math>(n-1)/4</math> liczb niebędących świadkami jej złożoności<ref name=":0" />.

== Przykład ==
Należy określić, czy liczba <math>n = 221</math> jest pierwsza.

Zapisując <math>n - 1 = 220</math> w postaci <math>2^2 \cdot 55,</math> otrzymuje się <math>s = 2</math> oraz <math>d = 55.</math> Następnie trzeba wybrać losowo liczbę <math>a < n.</math> Jeśli wylosowaną liczbą jest <math>a = 174,</math> wtedy dla <math>r</math> ze zbioru <math>\{0,1\}{:}</math>
* <math>a^{2{^0}\cdot d} \bmod n = 174^{55} \bmod 221 = 47 \neq 1,</math> i <math>\neq n - 1,</math> więc nierównoważne <math>-1 \bmod n.</math>
* <math>a^{2{^1}\cdot d} \bmod n = 174^{110} \bmod 221 = 220 = n - 1.</math>

Ponieważ <math>220 \equiv -1 \bmod n,</math> to albo liczba 221 jest pierwsza, albo 174 jest fałszywym świadkiem dla 221. W tym przypadku następuje losowanie kolejnej wartość <math>a,</math> tym razem <math>a = 137{:}</math>
* <math>a^{2{^0} \cdot d} \bmod n = 137^{55} \bmod 221 = 188 \neq 1</math> i <math>\neq n - 1,</math> więc nierównoważne <math>-1 \bmod n.</math>
* <math>a^{2{^1} \cdot d} \bmod n = 137^{110} \bmod 221 = 205 \neq n - 1.</math>

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:
: [[Największy wspólny dzielnik|NWD]](137−1, 221) = 17
: 221 / 17 = 13
: zatem 221 = 17 · 13

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

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 <math>n</math> udowodniono, że można test przeprowadzić znacznie szybciej<ref>Pomerance, C.; Selfridge, J. L. & Wagstaff, S. S., Jr. (1980), „The pseudoprimes to 25·10<sup>9</sup>”, Mathematics of Computation 35 (151): 1003–1026, [http://dx.doi.org/10.2307%2F2006210 doi:10.2307/2006210].</ref><ref>Jaeschke, Gerhard (1993), „On strong pseudoprimes to several bases”, Mathematics of Computation 61 (204): 915–926, [http://dx.doi.org/10.2307%2F2153262 doi:10.2307/2153262].</ref><ref>Zhang, Zhenxiang & Tang, Min (2003), „Finding strong pseudoprimes to several bases. II”, Mathematics of Computation 72 (44): 2085–2097, [http://dx.doi.org/10.1090%2FS0025-5718-03-01545-X doi:10.1090/S0025-5718-03-01545-X].</ref>:
* jeśli <math>n < 4\ 759\ 123\ 141,</math> wystarczy sprawdzić <math>a = 2, 7\ \mathrm i\ 61;</math>
* jeśli <math>n < 341\ 550\ 071\ 728\ 321,</math> wystarczy sprawdzić <math>a = 2, 3, 5, 7, 11, 13\ \mathrm i\ 17.</math>

(inne tego typu kryteria opisano np. w [https://archive.is/20120715150851/http://primes.utm.edu/prove/prove2_3.html The Prime Pages] i [http://miller-rabin.appspot.com 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 <math>a</math> nie wystarcza do testowania wszystkich liczb złożonych.

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
* {{MathWorld|adres=Rabin-MillerStrongPseudoprimeTest |tytuł=Rabin-Miller Strong Pseudoprime Test |data dostępu=12 grudnia 2020}}

{{Teoria liczb}}

{{Kontrola autorytatywna}}

[[Kategoria:Testy pierwszości|Millera-Rabina]]