Jako test pierwszości zastosowano dwa powszechnie znane algorytmy. Pierwszy sprawdza, czy badana liczba jest liczbą pseudopierwszą przy podstawie 2, czyli:
Drugi algorytm to test Millera-Rabina [3]. Próbuje on znaleźć świadectwo złożoności dla weryfikowanej liczbythen ZŁOŻONA
else PIERWSZA
witness(a, n) niech b[k...0] będzie binarną reprezentacją liczby n - 1 d := 1 for i := k downto 0 do x := d d := (d * d) mod n if (d = 1) i (x <> 1) i (x <> n - 1) then return ZŁOŻONA if b[i] = 1 then d := (d * a) mod n if d <> 1 then return ZŁOŻONA return PIERWSZATę procedurę wykorzystuje się w teście Millera-Rabina w następujący sposób:
Miller-Rabin(n, s) for i := 1 to s do a := Random (1, n - 1) (* losuje liczbę z przedziału [1...n-1] *) if witness (a, n) = ZŁÓŻONA then return ZŁOŻONA return PIERWSZA
Jeżeli otrzymano odpowiedź ZŁOŻONA, to jest to odpowiedź pewna;
jeżeli odpowiedź brzmiała PIERWSZA, to jest pierwsza
z dużym prawdopodobieństwem. Prawdopodobieństwo błędnej odpowiedzi możemy
regulować określając ile razy będziemy próbowali znaleźć świadka złożoności
liczby
. Można udowodnić, że dla dowolnej nieparzystej liczby
i dodatniej liczby
, oznaczającej liczbę prób znalezienia świadka
złożoności, prawdopodobieństwo tego, że procedura Miller-Rabin udzieli
złej odpowiedzi, nie przekracza
.
Istnieją oczywiście algorytmy deterministyczne udzielające odpowiedzi na pytanie,
czy liczba jest złożona. W roku 1983 Adleman, Pomerance i Rumely pokazali w swojej pracy [1]
algorytm działający w czasie
. Z kolei
w 1986 Goldwasser i Kilan przedstawili algorytm randomizowany działający
w oczekiwanym czasie wielomianowym dla prawie wszystkich danych wejściowych.
Jedną z zalet tego algorytmu było to, że jako pierwszy z algorytmów
randomizowanych wystawiał on certyfikat pierwszości, a nie certyfikat
złożoności liczby. Celem jednak było znalezienie algorytmu deterministycznego
działającego w czasie wielomianowym. 6 sierpnia 2002 Manindra Agrawal,
Neeraj Keyal i Nitin Saxena przedstawili pracę [2], w której pokazali,
że problem stwierdzenia, czy liczba jest pierwsza należy do klasy
złożoności
. Zaprezentowany przez nich algorytm działa w czasie
. Pokazali przy tym, że korzystając z hipotezy o gęstości
liczb pierwszych Sophie Germain (są to liczby pierwsze
, takie iż
też jest pierwsza) ich algorytm ma oczekiwany czas działania
.
Nie zdecydowałem się na implementację tego algorytmu, gdyż testu na pierwszość
liczby używam przy generacji kluczy, których postać jest podobna do liczb
pierwszych Sophie Germain. W mojej realizacji wystarczający jest dużo szybszy
(dla parametru
) test Millera-Rabina.