Test Millera-Rabina

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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: nieparzysta liczba naturalna do przetestowania;

parametr określający dokładność testu.

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

wylicz maksymalną potęgę dwójki dzielącą i przedstaw jako
powtórzyć razy:
wybrać losowo ze zbioru
jeśli i dla wszystkich ze zbioru zwróć wynik złożona.
zwróć wynik prawdopodobnie pierwsza.

Używając algorytmu szybkiego potęgowania można tę procedurę przeprowadzić w czasie , gdzie jest liczbą różnych testowanych wartości

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 jest liczbą pierwszą oraz, że

Niech dalej gdzie Wówczas albo albo istnieje dla którego [potrzebny przypis].

Liczbę która nie spełnia warunków powyższego twierdzenia nazywa się świadkiem złożoności liczby .

Twierdzenie 2[edytuj | edytuj kod]

Jeśli jest nieparzystą liczbą złożoną, to w zbiorze jest co najwyżej liczb nie będących świadkami jej złożoności[potrzebny przypis].

Przykład[edytuj | edytuj kod]

Należy określić, czy liczba jest pierwsza.

Zapisując w postaci otrzymuje się oraz Następnie trzeba wybrać losowo liczbę Jeśli wylosowaną liczbą jest wtedy dla ze zbioru

  • i więc nierównoważne

Ponieważ to albo liczba 221 jest pierwsza, albo 174 jest fałszywym świadkiem dla 221. W tym przypadku następuje losowanie kolejnej wartość tym razem

  • i więc nierównoważne

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 co najmniej 3/4 możliwych wartości jest dobrymi świadkami złożoności tej liczby. Jeśli zatem przeprowadzamy losowych prób, prawdopodobieństwo, że określimy liczbę złożoną jako pierwszą wynosi co najwyżej

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 udowodniono, że można test przeprowadzić znacznie szybciej[1][2][3]:

  • jeśli wystarczy sprawdzić
  • jeśli wystarczy sprawdzić

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

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  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.

Linki zewnętrzne[edytuj | edytuj kod]