Test Millera-Rabina

Test Millera-Rabinatest 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 i czas działaniaEdytuj

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ściEdytuj

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

Twierdzenie 1Edytuj

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 2Edytuj

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

PrzykładEdytuj

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 deterministyczneEdytuj

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

PrzypisyEdytuj

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