We współczesnej kryptografii w wielu sytuacjach wymagana jest duża losowa liczba pierwsza. Omówiony właśnie kryptosystem RSA jest takim przykładem.
Test pierwszości to algorytm determinujący, czy liczba podana na wejściu jest pierwsza. Wszystkie testy pierwszości szukają, tak naprawdę, świadka na złożoność liczby. Jeśli go nie znajdą odpowiadają, że liczba jest pierwsza. Powszechnie rozważane są dwa rodzaje testów pierwszości:
Jest istotna różnica pomiędzy stwierdzeniem, że liczba jest złożona (poprzez brak zaliczenia testu pierwszości), a wskazaniem jej rozkładu (faktoryzacją). W szczególności istnieje efektywny (wielomianowy) algorytm testujący pierwszość natomiast dotychczas poznane algorytmy faktoryzujące są o wiele wolniejsze.
To najprostszy deterministyczny test pierwszości. Daną na wejściu liczbę \( n \) wydziela kolejno przez \( m=2,3,\ldots,\lfloor \sqrt{m}\rfloor \). Jeśli przy którymkolwiek dzieleniu reszta równa jest \( 0 \) test zwraca, że \( n \) jest złożona w przeciwnym wypadku, że \( n \) jest pierwsza. Zwróćmy uwagę, że jeśli \( n \) okaże się złożona, to znajdziemy także nietrywialny jej dzielnik. Niestety jest to bardzo wolna metoda sprawdzania pierwszości - wymaga \( O(\sqrt{n}\lg^2{n}) \) kroków.
Probabilistyczne testy pierwszości działają według następującego schematu:
Małe Twierdzenia Fermata mówi, że jeśli \( n \) jest pierwsza, to dla dowolnego \( b\in{\{ {1,2,\ldots,n-1} \} } \) zachodzi
\( b^{n-1}\ \equiv_{n}1 . \)
Powyższe zdanie może być prawdziwe dla pewnych złożonych \( n \) i pewnych \( 1 < b < n \). Jeśli jednak dla danego \( n \) i pewnego \( 1 < b < n-1 \), tożsamość \( b^{n-1}\ \equiv_{n}1 \) nie zachodzi, to \( n \) jest złożona i \( b \) jest świadkiem złożoności.
Liczba pseudopierwsza przy podstawie \( b \) to złożona liczba nieparzysta \( n \) taka, że:
Przykład
Liczba \( 91=7\cdot13 \) jest pseudopierwsza przy podstawie \( 3 \).
Zatem \( 3^{90}\ \equiv_{91}1 \), czyli \( 91 \) jest pseudopierwsze przy podstawie \( 3 \).
Sprawdźmy, czy \( 91 \) jest również pseudopierwsze przy podstawie \( 2 \).
Zatem \( 2^{90}\not\equiv_{91}1 \). Gdybyśmy nie wiedzieli, że \( 91 \) jest złożona, byłby to dowód tego faktu (\( 2 \) jest świadkiem złożoności \( 91 \)).
Zauważmy, że dla dowolnego \( n \), wszystkie podstawy pseudopierwszości \( n \) znajdują się w grupie \( \mathbb{Z}_n^{*}=(\mathbb{Z}_n^{*},\cdot,1) \) elementów odwracalnych względem mnożenia modulo \( n \), bo \( bb^{n-2}\equiv_n 1 \) oznacza, że \( b^{n-2}= b^{-1} \). W szczególności podstawy takie są względnie pierwsze z \( n \).
Obserwacja 7.2
Dla złożonej nieparzystej liczby \( n \) zachodzi:
wtedy i tylko wtedy, gdy rząd \( b \) w \( \mathbb{Z}_n^{*} \) (tzn. najmniejsza, dodatnie \( k \) takie, że \( b^k\equiv_n 1 \)) dzieli \( n-1 \),
Dowód
Dla dowodu punktu pierwszego niech \( k \) będzie rzędem \( b \) w \( \mathbb{Z}_n^* \) oraz \( n-1=q\cdot k+r \), gdzie \( 0\leq r < k \). Wtedy
\( 1\equiv_n b^{n-1}\equiv_n b^{qk+r}\equiv_nb^{qk}b^r\equiv_nb^r. \)
Zatem \( b^r\equiv_n 1 \), ale ponieważ \( r < k \) i \( k \) jest najmniejszą dodatnią liczbą spełniającą \( x^k\equiv_n1 \) to \( r=0 \) i \( k|n-1 \).
Dla dowodu drugiego punktu załóżmy, że \( n \) jest pseudopierwsze przy obu podstawach \( b_1 \) oraz \( b_2 \), czyli \( b_1^{n-1}\ \equiv_{n}1 \) i \( b_2^{n-1}\ \equiv_{n}1 \). Po pomnożeniu tych kongruencji otrzymujemy \( (b_1b_2)^{n-1}\equiv_n1 \), czyli \( n \) jest pseudopierwsze przy podstawie \( b_1b_2 \). Mnożąc zaś \( b_1^{n-1}\equiv_n b_2^{n-1} \) przez \( (b_2^{-1})^{n-1} \) otrzymujemy \( (b_1b_2^{-1})^{n-1}\equiv_n1 \), co było do pokazania.
Wreszcie, załóżmy, że \( {\{ {b_1,\ldots,b_m} \} } \) to zbiór wszystkich podstaw, przy których \( n \) jest pseudopierwsze i \( 1 < b_i < n \). Niech \( b \) będzie świadkiem złożoności \( n \). Wtedy \( bb_i \) nie może być podstawą pseudopierwszości \( n \). Rzeczywiście, gdyby było, to drugi punkt dawałby, że \( bb_ib_i^{-1}=b \) też musiałoby być. Sprzeczność. A zatem mamy przynajmniej \( m \) różnych świadków pierwszości \( bb_1,\ldots,bb_m \), co było do pokazania.
Na podstawie ostatnich rozważań opiszemy probabilistyczny test pierwszości, znany jako test pierwszości Fermata. Mając daną na wejściu liczbę \( n \):
Jeśli nie, to \( n \) jest złożona i \( b \) jest świadkiem złożoności \( n \). Jeśli tak, to \( n \) przechodzi test.
Załóżmy, że wykonaliśmy \( k \) powtórzeń. Wtedy zgodnie z Obserwacją 7.2 szansa na to, że \( n \) nie ma świadka złożoności wynosi \( \frac{1}{2^k} \). To jednak nie oznacza, że z taką szansą \( n \) jest pierwsza. Okazuje się, że istnieją liczby które nie mają świadka złożoności, a mimo to są złożone.
Liczba Carmichaela to liczba złożona, która nie ma świadków złożoności. Zatem liczba \( n \) jest liczbą Carmichaela jeśli
\( b^{n-1}\equiv_n 1. \)
Oto lista kilku pierwszych liczb Carmichaela:
\( 561,1105,1729,2465,2821,6601,8911,\ldots. \)
Liczbami o tych właściwościach zajmował się już Korselt pod koniec XIX wieku. Co ciekawe nie wiedział on czy takie liczby w ogóle istnieją. Niemniej podał on następującą ich charakteryzację.
Twierdzenie 7.3 [Korselt 1899]
Liczba złożona \( n \) jest liczbą Carmichaela wtedy i tylko wtedy, gdy \( n \) nie jest podzielna przez żaden kwadrat liczby pierwszej i dla wszystkich dzielników pierwszych \( p \) liczby \( n \) zachodzi \( p-1|n-1 \).
Dowód
Załóżmy najpierw, że \( p^2|n \) dla pewnej liczby pierwszej \( p \). Ponieważ elementy odwracalne w \( (\mathbb{Z}_{p^2}, \cdot) \) to dokładnie względnie pierwsze z \( p^2 \), więc grupa \( \mathbb{Z}_{p^2}^{*} \) ma \( \varphi(p^2)=p(p-1) \) elementów. Gdy \( p=2 \) to grupa ta ma \( 2 \) elementy więc jest cykliczna. Niech więc \( g \) będzie jej generatorem, tzn. jedynym elementem rożnym od \( 1 \). Dla \( p\neq 2 \) niech \( g=p-1 \). Ponieważ
\( g^p = (p-1)^p = \sum_{i=0}^p {p \choose i}p^i (-1)^{p-i} \)
i wszystkie składniki poza \( i=0,1 \) są podzielne przez \( p^2 \), to
\( g^p = 1 + {p \choose 1}(-1)^{p-1} = 1+p^2 \equiv_{p^2} =1. \)
Oznacza to, że \( g \) jest odracalnym elementem \( \mathbb{Z}_{p^2}^{*} \) i wobec \( g \neq 1 \) rząd \( g \) wynosi \( p \).
Niech \( n' \) będzie iloczynem wszystkich liczb pierwszych dzielących \( n \) poza samą liczbą \( p \). Wtedy, oczywiście \( {\sf NWD}(p^2,n')=1 \) i z Chińskiego Twierdzenia o Resztach wiemy, iż istnieje \( b \) takie, że
\( \begin{align*} b & \equiv_{p^2} & g, \\ b & \equiv_{n'} & 1. \end{align*} \)
W szczególności
\( {\sf NWD}(b,n)=1, \)
gdyż \( p \) nie dzieli \( b \) (jako, że \( b\equiv_{p^2}g \) a \( g \) leżąc w \( \mathbb{Z}_{p^2}^{*} \) nie może być wielokrotnością \( p \)) i żadna inna liczba pierwsza z rozkładu \( n \) nie dzieli \( p \), bo \( b\equiv_{n'}1 \). Ponieważ \( n \) jest liczbą Carmichaela, to \( b^{n-1}\equiv_n1 \). A zatem \( g^{n-1}\equiv_{p^2}b^{n-1}\equiv_{p^2}1 \). Ale ponieważ \( g \) ma rząd \( p \) w grupie \( \mathbb{Z}_{p^2}^{*} \), to \( p|n-1 \), co stoi w sprzeczności z \( p|n \). Udowodniliśmy zatem, że liczby Carmichaela rozkładają się na iloczyn różnych liczb pierwszych.
Niech teraz \( p|n \) i \( p-1∤ n-1 \). Ponieważ \( p^2∤ n \), to \( p \) i \( \frac{n}{p} \) są względnie pierwsze. Grupa \( \mathbb{Z}_p^* \) jest grupą multyplikatywną ciała \( {\bf GF}(p) \), więc jest cykliczna. Niech \( g \) będzie jej generatorem. Znów, z Chińskiego Twierdzenia o Resztach, mamy \( b \) takie, że
\( \begin{align*} b & \equiv_{p} & g, \\ b & \equiv_{\frac{n}{p}} & 1. \end{align*} \)
Oczywiście \( {\sf NWD}(b,n)=1 \). Ponieważ \( n \) jest liczbą Carmichaela, to wtedy \( b^{n-1}\equiv_n1 \). Ale \( b^{n-1}\equiv_pg^{n-1}\not\equiv_p1 \), gdyż \( g \) ma rząd \( p-1 \), a \( p-1∤ n-1 \).
Na odwrót, niech \( n \) będzie iloczynem różnych liczb pierwszych \( p \), i to takich, że \( p-1|n-1 \). Chcemy pokazać, że dowolne \( b\perp n \) jest podstawą pseudopierwszości dla \( n \). Zauważmy, że \( b^{n-1} \) jest potęgą liczby \( b^{p-1} \), a Twierdzenie Fermata daje \( b^{p-1}\equiv_p 1 \). To oznacza, że \( b^{n-1}\equiv_p 1 \) dla wszystkich liczb pierwszych \( p|n \). Ponieważ \( n \) nie dzieli się przez kwadrat żadnej liczby pierwszej, to \( b^{n-1}\equiv_n 1 \).
Wniosek 7.4
Liczba Carmichaela jest iloczynem przynajmniej trzech różnych liczb pierwszych.
Dowód
Opierając się na Twierdzeniu 7.3 wystarczy pokazać, że jeśli \( n=pq \) dla różnych liczb pierwszych \( p,q \), to \( n \) nie jest liczbą Carmichaela. Bez straty ogólności przyjmijmy, iż \( p < q \). Gdyby \( n \) była liczbą Carmichaela to \( q-1|n-1 \) ale \( n-1=p(q-1)+p-1\equiv_{q-1}p-1 \). Sprzeczność.
Przykład
Liczba \( 561 \) jest liczbą Carmichaela ponieważ
Jak dużo jest liczb Carmichaela? Pierwszą taką liczbę wskazał Robert Carmichael w 1910 i była to liczba \( 561 \). Liczby Carmichaela okazują się bardzo rzadkie. W przedziale \( [1,\ldots,10^7] \) jest ich jedynie \( 585 355 \), czyli średnio jedna liczba Carmichaela na 170 bilionów liczb naturalnych. Dopiero w 1994 udowodniono, że jest ich nieskończenie wiele.
Podsumujmy naszą wiedzę o probabilistycznym teście Fermata. Poddając \( k \) krotnie liczbę \( n \) temu testowi:
Test Millera-Rabina bazuje na koncepcji silnej pseudopierwszości, którą zdefiniujemy poniżej. Niech \( n \) będzie pseudopierwsza przy podstawie \( b \), czyli \( b^{n-1}\equiv_n1 \). Zauważmy, że jeśli \( n \) jest pierwsza, to w ciągu
\( b^{(n-1)/2} {\sf mod} n ,\quad b^{(n-1)/4} {\sf mod} n , \quad \ldots \quad b^{(n-1)/2^s} {\sf mod} n , \)
gdzie \( s \) jest tak dobrane że \( (n-1)/2^s \) jest nieparzysta, pierwsza wartość modulo \( n \) różna od \( 1 \) to \( -1 \). Wynika to z następującej obserwacji.
Obserwacja 7.5
Dla dowolnej liczby pierwszej \( p \) jeśli \( x^2\equiv_p 1 \), to \( x\equiv_p \pm1 \).
Dowód
Załóżmy, ze \( x^2\equiv_p1 \). Wtedy \( (x-1)(x+1)\equiv_p 0 \), czyli \( p|(x-1)(x+1) \). Ponieważ \( p \) jest pierwsza, to musi ona dzielić jedną z liczb \( x-1 \) lub \( x+1 \). To jest z kolei równoważne z \( x\equiv_p1 \) lub \( x\equiv_p-1 \).
W praktyce ciąg ten analizowany jest z drugiej strony. Niech \( n-1=2^st \), gdzie \( t \) jest nieparzysta. Najpierw obliczamy \( b^t {\sf mod} n \) później (jeśli otrzymaliśmy coś różnego jest od \( 1 \)) obliczamy \( b^{2t} {\sf mod} n \), później \( b^{4t} {\sf mod} n \), aż otrzymamy wartość \( 1 \). Wtedy jeśli poprzednia wartość jest różna od \( -1 \), to \( n \) jest złożona.
Niech \( n \) będzie nieparzystą liczbą złożoną i niech \( n-1=2^st \), gdzie \( t \) jest nieparzysta, \( b\in{\{ {1,2,\ldots,n-1} \} } \). Jeśli
to \( n \) jest silnie pseudopierwsza przy podstawie \( b \).
Oczywiście, wprost z definicji, każda liczba silnie pseudopierwsza przy podstawie \( b \) jest też pseudopierwsza przy podstawie \( b \).
Sformułujemy najpierw algorytm testu, a później udowodnimy, że - po kilku powtórzeniach - z bardzo dużym prawdopodobieństwem odróżni on liczbę pierwszą od złożonej. Test ten nie ma żadnych wyjątków typu liczby Carmichaela w teście Fermata!
Dla danej na wejściu liczby nieparzystej \( n \) algorytm działa następująco:
\( b^{2t} {\sf mod} n ,2^{2^2t} {\sf mod} n ,2^{2^3t} {\sf mod} n ,\ldots,2^{2^{s-1}t} \ {\sf mod} n , \)
aż otrzymasz \( -1 \). Jeśli uzyskałeś \( -1 \), to \( n \) przechodzi test. Jeśli zaś \( -1 \) nie wystąpiło w obliczonym ciągu, to \( n \) jest złożona i \( b \) jest świadkiem złożoności. Zatem wykonanych będzie co najwyżej \( O(\lg{n}) \) kroków i w każdym kroku przeprowadzamy szybkie potęgowanie w \( O(\lg^3{n}) \), czyli sumaryczny czas to \( O(\lg^4{n}) \).
W praktyce licząc kolejne wyrazy \( b^{2t} {\sf mod} n ,2^{2^2t} {\sf mod} n ,2^{2^3t} {\sf mod} n ,\ldots \) jeśli otrzymamy na którymś miejscu \( 1 \) (a wcześniej nie było \( -1 \)), to możemy przerwać test i zwrócić, że \( n \) jest złożona (gdyż pozostałe wyrazy ciągu pozostaną równe \( 1 \)).
Przykład
Wykonajmy test Millera-Rabina dla \( n=561 \) (jest to najmniejsza liczba Carmichaela, nieodróżnialna od liczb pierwszych testem Fermata):
Wykład ten zakończymy podaniem twierdzenia (bez dowodu), uzasadniajacego, że jeśli liczba nieparzysta \( n \) przeszła \( k \) testów Millera-Rabina to liczba \( n \) jest złożona z prawdopodobieństwem jedynie \( \frac{1}{4^k} \). A więc po \( 10 \) testach Millera-Rabina \( n \) jest złożona z prawdopodobieństwem \( 0.0000009 \).
Twierdzenie 7.6
Jeśli \( n \) jest nieparzystą liczbą złożoną, to \( n \) jest silnie pseudopierwsze dla co najwyżej \( 25\% \) liczb \( b\in{\{ {1,\ldots,n-1} \} } \).
W praktyce okazuje się, że prawie we wszystkich wypadkach wystarczy kilka testów Millera-Rabina. Na przykład policzono, że jest tylko jedna złożona liczba nieparzysta mniejsza od \( 2.5\cdot10^{10} \), konkretnie 3215031751, która jest silnie pseudopierwsza dla podstaw \( 2,3,5 \) i \( 7 \). Mimo to matematycy wciąż szukają szybkich deterministycznych testów pierwszości. Niedawno, w roku 2002, Agrawal, Kayal i Saxena pokazali pierwszy, efektywny \( O(\lg^{12}{n}) \) deterministyczny test pierwszości. Po pewnych przeróbkach algorytm ten działa w czasie \( O(\lg^6{n}) \)). Jednak w praktyce algorytm ten jest dużo wolniejszy od szybkich testów probabilistycznych. Z drugiej strony, jeśli prawdziwa jest Uogólniona Hipoteza Riemanna, to każda nieparzysta, złożona liczba \( n \) ma świadka złożoności \( b \) w teście Millera-Rabina takiego, że \( 0 < b < 2\log^2{n} \). To oznaczałoby, że test Millera-Rabina jest testem deterministycznym i to działającym bardzo szybko.