3 Generator liczb losowych, liczby pierwsze

W pracy korzystano z generatora liczb losowych zaimplementowanego w bibliotece random dostarczanej w systemie Ocaml. Przy jego użyciu generowano kolejne dwu bajtowe części liczby, która jest tworzona. W rzeczywistości prawo polskie wymaga, by w wielu etapach tworzenia podpisu elektronicznego używać sprzętowych generatorów ciągów losowych. Korzystanie z generatora programowego umożliwia bowiem dokonywanie powtarzalnych testów, co narusza zasadę bezpieczeństwa.

Jako test pierwszości zastosowano dwa powszechnie znane algorytmy. Pierwszy sprawdza, czy badana liczba jest liczbą pseudopierwszą przy podstawie 2, czyli:

$if \;\;\; 2^{p - 1} \not\equiv 1 \;\;\; mod \;\;\;p\;\;$ then ZŁOŻONA
else PIERWSZA

Drugi algorytm to test Millera-Rabina [3]. Próbuje on znaleźć świadectwo złożoności dla weryfikowanej liczby $p$. Do znalezienia takiego świadka używamy funkcji witness(a, n). Wykonuje ona algorytm podobny do testu Fermata, jednak zamiast $2^{p-1}\;$ obliczamy $a^{p-1} \;$. Dodatkowo na każdym kroku obliczeń sprawdzamy, czy nie znaleźliśmy nietrywialnego pierwiastka kwadratowego z $1$.

    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 PIERWSZA

Tę 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 $n$ 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 $n$. Można udowodnić, że dla dowolnej nieparzystej liczby $n > 2$ i dodatniej liczby $s$, oznaczającej liczbę prób znalezienia świadka złożoności, prawdopodobieństwo tego, że procedura Miller-Rabin udzieli złej odpowiedzi, nie przekracza $2^{-s}$.

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 $log(n)^{O(log \; log \; log (n))}$. 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 $\mathbb{P}$. Zaprezentowany przez nich algorytm działa w czasie $O(log(n))^{12}$. Pokazali przy tym, że korzystając z hipotezy o gęstości liczb pierwszych Sophie Germain (są to liczby pierwsze $p$, takie iż $2p + 1$ też jest pierwsza) ich algorytm ma oczekiwany czas działania $O(log (n))^6$. 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 $s = 60$) test Millera-Rabina.