Processing math: 16%

Testowanie pierwszości

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:

  • deterministyczne - wydają certyfikat pierwszości; odpowiadają że podana na wejściu liczba n jest pierwsza wtedy i tylko wtedy gdy naprawdę tak jest,
  • probabilistyczne - przepuszczają pewne liczby złożone (stwierdzając ich pierwszość), nigdy jednak nie mylą się na liczbach pierwszych.

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.

Naiwny test pierwszości.

To najprostszy deterministyczny test pierwszości. Daną na wejściu liczbę n wydziela kolejno przez m=2,3,,m. 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(nlg2n) kroków.

Probabilistyczne testy pierwszości działają według następującego schematu:

  • Wybierz losowe a{0,1,2,,n1}.
  • Sprawdź pewną tożsamość dotyczącą liczb a i n, a zależącą od konkretnego testu. Jeśli tożsamość jest fałszywa, to n jest złożona i a jest świadkiem złożoności (ale niekoniecznie dzielnikiem liczby n). Jeśli zaś tożsamość jest prawdziwa, to a przechodzi test (co niekoniecznie oznacza, ze jest pierwsza).

Liczby pseudopierwsze i test Fermata

Małe Twierdzenia Fermata mówi, że jeśli n jest pierwsza, to dla dowolnego b{1,2,,n1} zachodzi

bn1 n1.

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<n1, tożsamość bn1 n1 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:

  • 1b<n,
  • bn,
  • bn1 n1.

Przykład

Liczba 91=713 jest pseudopierwsza przy podstawie 3.

  • 391,
  • φ(91)=φ(7)φ(13)=612=72,
  • z Twierdzenia Eulera mamy 390913171+1891318,
  • liczymy 318mod91 metodą szybkiego potęgowania:
    • 18=(10010)2,
    • 32=9,
    • 34=99=81,
    • 38=8181=6561919,
    • 3169199=81.
  • 318=3163291819=729911.

Zatem 390 911, czyli 91 jest pseudopierwsze przy podstawie 3.

Sprawdźmy, czy 91 jest również pseudopierwsze przy podstawie 2.

  • 291 a zatem znów z Twierdzenia Eulera 29091218,
  • liczymy 218mod91 metodą szybkiego potęgowania:
    • 18=(10010)2,
    • 22=4,
    • 24=44=16,
    • 28=1616=2569174,
    • 216917474=54769116.
  • 218=2162291162=32.

Zatem 290. 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:

  • Jeśli 1 < b < n oraz b\perp n , to n jest pseudopierwsza przy podstawie b

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 ,

  • Jeśli n jest pseudopierwsza przy podstawach b_1, b_2\perp n ,to n jest pseudopierwsza przy podstawie b_1b_2 oraz b_1b_2^{-1} (gdzie b_2^{-1} jest odwrotnością b_2 w \mathbb{Z}_n^{*} ),
  • Jeśli n ma świadka złożoności, to przynajmiej połowa elementów w b\in{\{ {1,\ldots,n-1} \} } jest świadkiem złożoności.

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.

Test pierwszości Femata.

Na podstawie ostatnich rozważań opiszemy probabilistyczny test pierwszości, znany jako test pierwszości Fermata. Mając daną na wejściu liczbę n :

  • Wylosuj b\in{\{ {1,2,\ldots,n-1} \} } .
  • Sprawdź algorytmem Euklidesa ( O(\lg^3{n}) ) czy d={\sf NWD}(b,n)>1 . Jeśli tak, to n jest złożona, co więcej d jest nietrywialnym dzielnikiem n .
  • Sprawdź czy b^{n-1}\equiv_n 1 . Metodą szybkiego potęgowania można to zrobić w czasie O(\lg^3{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

  • n jest złożona,
  • dla dowolnego b\in{\{ {1,\ldots,n-1} \} } takiego, że b\perp n zachodzi

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ż

  • 561=3\cdot11\cdot17 , czyli żadna liczba pierwsza w rozkładzie się nie powtarza,
  • 2|560 , 10|560 , 16|560 .

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:

  • albo został znaleziony świadek złożności (bądź nawet dzielnik) i n jest na pewno złożona,
  • albo trafiliśmy k razy na podstawę pseudopierwszości n i z prawdopodobieństwem 1-\frac{1}{2^k} liczba n jest pierwsza bądź jest liczbą Carmichaela.

Test pierwszości Millera-Rabina

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

  • b^t\ \equiv_{n}1 lub
  • istnieje r takie, że 0\leq r < s i b^{2^rt}\equiv_n-1 ,

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 .

Test pierwszości Miller'a-Rabin'a.

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:

  • Wylicz liczbę nieparzystą t taką, że n-1=2^st ,
  • Wylosuj liczbę b\in{\{ {2,\ldots,n-1} \} } ,
  • Oblicz b^t {\sf mod} n , (metodą szybkiego potęgowania w O(\lg^3{n}) )
  • jeśli otrzymałeś \pm1 , to n przechodzi test,
  • w przeciwnym przypadku licz kolejno

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):

  • n-1=561-1=2^4\cdot35 , czyli s=4 i t=35 ,
  • wykonajmy test dla najmniejszej sensownej podstawy, czyli 2 :
    • 2^{35}\equiv_{561}? ,
    • 35=(100011)_2 ,
    • 2^2=4 ,
    • 2^4=16 ,
    • 2^8=256 ,
    • 2^{16}=65536\equiv_{561}460 ,
    • 2^{32}\equiv_{561}460\cdot460=211600\equiv_{561}103 ,
    • 2^{35}=2^{32}\cdot2^2\cdot2^1\equiv_{561}103\cdot4\cdot2\equiv_{561}263 .
  • ponieważ 2^{35}\not\equiv_{561}\pm1 sprawdzamy kolejne potęgi...
  • 2^{70}\equiv_{561}263\cdot263=166 ,
  • 2^{140}\equiv_{561}166\cdot166=67 ,
  • 2^{280}\equiv_{561}67\cdot67=1 . W sekwencji tej znalazła się wartość 1 , a przed nią nie było -1 . Zatem 2 jest świadkiem złożoności 561 w teście Millera-Rabina.

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.