Test Millera-Rabina

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Test Millera-Rabina jest testem pierwszości, czyli algorytmem określającym 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 i czas działania[edytuj | edytuj kod]

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

Wejście: n > 1: nieparzysta liczba naturalna do przetestowania; k: parametr określający dokładność testu
Wyjście: złożona jeśli 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 i przedstaw n-1 jako 2^s \cdot d;
powtórz k razy:
wybierz a losowo ze zbioru \{ 1,2,\dots, n - 1\}
jeśli a^d \not\equiv 1\ \bmod\ n i a^{{2^r}d} \not\equiv\ -1\ \bmod\ n dla wszystkich r ze zbioru \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żemy tę procedurę przeprowadzić w czasie O(k × log3 n), gdzie k jest liczbą różnych wartości a które testujemy.

Dowód poprawności[edytuj | edytuj kod]

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

Twierdzenie 1[edytuj | edytuj kod]

Załóżmy, że n jest liczbą pierwszą oraz, że a\in\mathbb{Z}_n^\star. Niech dalej d=(n-1)/2^s, gdzie s=\max\{j:\;2^j|(n-1)\}. Wówczas albo a^d\equiv1 \pmod n, albo istnieje r\in\mathbb Z_s, dla którego a^{2^r\cdot d}\equiv-1\pmod n[potrzebne źródło].

Liczbę 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

Twierdzenie 2[edytuj | edytuj kod]

Jeśli n\ge3 jest nieparzystą liczbą złożoną, to w zbiorze \mathbb Z_n^\star jest co najwyżej (n-1)/4 liczb nie będących świadkami jej złożoności[potrzebne źródło].

Przykład[edytuj | edytuj kod]

Załóżmy, że chcemy określić, czy liczba n = 221 jest pierwsza. Zapiszemy n − 1 = 220 w postaci 22·55, czyli s = 2 oraz d = 55. Losowo wybieramy liczbę a < n. Załóżmy, że wylosowaliśmy a = 174. Obliczamy:

  • a20·d mod n = 17455 mod 221 = 47 ≠ 1, n − 1
  • a21·d mod n = 174110 mod 221 = 220 = n − 1.

Ponieważ 220 ≡ −1 mod n, albo liczba 221 jest pierwsza, albo 174 jest fałszywym świadkiem dla 221. Spróbujemy inną losową wartość a, tym razem a = 137:

  • a20·d mod n = 13755 mod 221 = 188 ≠ 1, n − 1
  • a21·d mod n = 137110 mod 221 = 205 ≠ 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

Dokładność testu i wersje deterministyczne[edytuj | edytuj kod]

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

Istnieją deterministyczne wersje tego testu, jednak w ogólności są znacznie wolniejsze od niego i nie mają zastosowania praktycznego. Dla małych n udowodniono, że można test przeprowadzić znacznie szybciej[1][2][3]:

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

(inne tego typu kryteria opisane są w [1], [2])

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 nie wystarcza do testowania wszystkich liczb złożonych.

Linki zewnętrzne[edytuj | edytuj kod]

Przypisy

  1. Pomerance, C.; Selfridge, J. L. & Wagstaff, S. S., Jr. (1980), "The pseudoprimes to 25·109", Mathematics of Computation 35 (151): 1003–1026, doi:10.2307/2006210
  2. Jaeschke, Gerhard (1993), "On strong pseudoprimes to several bases", Mathematics of Computation 61 (204): 915–926, doi:10.2307/2153262
  3. Zhang, Zhenxiang & Tang, Min (2003), "Finding strong pseudoprimes to several bases. II", Mathematics of Computation 72 (44): 2085–2097, doi:10.1090/S0025-5718-03-01545-X