algorytm.org

Test pierwszości - test Millera-Rabina



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Test pierwszości - test Millera-Rabina
Ocena użytkowników:***** / 31
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 26 kwietnia 2007 21:35

Test pierwszości Millera-Rabina to probabilistyczny test umożliwiający sprawdzenie czy dana liczba jest złożona czy prawdopodobnie pierwsza. Metoda, w oparciu o którą powstała to deterministyczny algorytm Millera, którego poprawność zależy od nieudowodnionej uogólnionej hipotezy Riemanna. Michael O. Rabin zmodyfikował ten algorytm do postaci testu probablistycznego i dowiódł jego poprawności w tej postaci. Algorytm używany jest do sprawdzania wyłącznie liczb nieparzystych (liczby parzyste - za wyjątkiem dwójki - w sposób oczywisty nie są liczbami pierwszymi). Test Millera-Rabina można zapisać następująco:
k- określa dokładność testu
n - nieparzysta liczba do sprawdzenia

Wylicz s - maksymalną potęgę dwójki dzielącą n-1.
Podstaw d = n/2s
powtórz k razy:
  wylosuj a takie, że 1<a<n
  sprawdź czy ad mod n różne od 1
  jeżeli tak to sprawdz czy ad*2r mod n rozne od n-1 dla wszystkich r, takich że: 0≤r≤s-1
     jeżeli tak to to przerwij test - liczba nie jest pierwsza
jeżeli nie przerwano testu dla żadnej z prób to liczba prawdopodobnie jest pierwsza

Na pierwszy rzut oka trudność sprawiać może obliczenie wartości ab mod n, szczególnie dla dużych wartości b. Szybko i bezproblemowo obliczymy taką wartość używając algorytmu szybkiego potęgowania modularnego lub dużo wolniejszego, ale prostszego algorytmu naiwnego potęgowania modularnego.

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.

Przykład:

Sprawdzimy z dokładnością k=3, czy liczba n=13 jest pierwsza.
Najpierw obliczymy maksymalną potęge dwójki dzielącą n-1.
12 mod 2 = 0, 12 mod 4 = 0, 12 mod 8 != 0. Zatem maksymalną potęgą dwójki dzielącą 12 jest 4, czyli 4=2s, s=2.
Obczliymy teraz d = 13/4 = 3 (dzielenie całkowitoliczbowe).
Pierwsza próba a=2.
23 mod 13 = 8, jest różne od 1, zatem przechodzimy do drugiego sprawdzenia.
r = 0, 23 mod 13 = 8.
r = 1, 26 mod 13 = 12.
Dla r = 1, ad*2r mod n równe jest n-1, zatem kontuujemy test.
Druga próba a=6.
63 mod 13 = 8, jest różne od 1, zatem przechodzimy do drugiego sprawdzenia.
r = 0, 63 mod 13 = 8.
r = 1, 66 mod 13 = 12.
Dla r = 1, ad*2r mod n równe jest n-1, zatem kontuujemy test.
Trzecia próba a=11.
113 mod 13 = 5, jest różne od 1, zatem przechodzimy do drugiego sprawdzenia.
r = 0, 113 mod 13 = 5.
r = 1, 116mod 13 = 12.
Dla r = 1, ad*2r mod n równe jest n-1, zatem kontuujemy test.
Wykonaliśmy wszystkie próby, nie stwiedziliśmy, że liczba jest złożona, zatem 13 jest prawdopodobnie liczbą pierwszą.

Sprawdzimy z dokładnością k=3, czy liczba n=9 jest pierwsza.
Najpierw obliczymy maksymalną potęge dwójki dzielącą n-1.
8 mod 2 = 0, 8 mod 4 = 0, 8 mod 8 = 0, 8 mod 16 != 0. Zatem maksymalną potęgą dwójki dzielącą 8 jest 8, czyli 8=2s, s=3.
Obliczymy d = 8/8 = 1.
Pierwsza próba a=2.
21 mod 9 = 2, jest różne od 1, zatem przechodzimy do drugiego sprawdzenia.
r = 0, 21 mod 9 = 2.
r = 1, 22 mod 9 = 4.
r = 2, 24 mod 9 = 7.
Wyniki drugiego sprawdzenia są różne od n-1 dla wszystkich r, zatem liczba 9 nie jest liczbą pierwszą, możemy przerwać test.



Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 2
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 3
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 13
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 2
Tomasz LubińskiJava
.java
.java
***** / 4
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 26 maja 2010 22:28
Komentarze
photo
+1 # ŁukaszT 2014-01-27 19:35
mam pytanie:
Podstaw d = n/2^s
Czy tam nie powinno być n-1?
Na wikipedii jest tak
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Tomasz Lubiński 2015-09-04 09:43
Przy założeniu że / oznacza dzielenie całkowitoliczbo we (odrzucamy część ułamkową), wynik d = n/2^s oraz d = (n-1)/2^s będzie taki sam. Skoro nie musimy odejmować żeby uzyskać prawidłowy wynik to tego nie robimy :)

Ponieważ z definicji n-1 dzieli się przez 2^s, to n podzieli się przez 2^s i da 1/2^s reszty.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # DawidDawidziak 2018-04-19 08:33
Witam wydaję mi się że ten krok jest błędny:
- sprawdź czy a^d mod n różne od 1.

Załóżmy że sprawdzamy czy liczba 13 jest liczbą pierwszą.
Wtedy d = 13/2^2 = 13/4 = 3
Następnie jako liczbę a wylosujemy 3 to wychodzi nam w tym kroku tak

3^3 = 27
27 mod 13 = 1 i test zostaje przerwany, co oznacza że liczba 13 nie jest liczbą pierwszą.
Proszę o komentarz czy się nie mylę.

Pozdrawiam
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Tomasz Lubiński 2019-11-29 08:00
Jeżeli a^d mod n wychodzi 1 to nie przerywamy testu, tylko kontynuujemy bez dodatkowego sprawdzania czy a^(d*2^r) mod n jest różne od n-1 dla wszystkich r takich, że r = 0, 1, ..., s-1.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz