Kryptografia jest dziedziną informatyki, zajmującą się zagadnieniami bezpieczeństwa informacji. W szczególności kryptografia traktuje o: kodowaniu/dekodowaniu, autoryzacji, kontroli dostępu. W drugiej połowie XX wieku kryptografia całkowicie zmieniła swoje oblicze, głównie dzięki stworzeniu kryptosystemów o publicznym kluczu. Obecnie jest to dziedzina, w której znajduje zastosowanie wiele rozważań z teorii informacji, złożoności obliczeniowej, statystyki, kombinatoryki i, na co zwracamy uwagę, z teorii liczb.
W tym wykładzie przedstawiamy, bardzo pobieżnie, model matematyczny kodowania/dekodowania wiadomości. Później opisujemy dwa kryptosystemy: Cezara (bardziej jako przykład dydaktyczny) oraz RSA. W drugiej części wykładu poznamy algorytmy sprawdzające czy liczba jest pierwsza.
Rozważamy zagadnienie kryptograficzne polegające na przesłaniu wiadomości, od nadawcy do obiorcy, w taki sposób, by żadna trzecia (przypadkowa) osoba nie była w stanie jej odczytać.
Tekst jawny to ciąg symboli (znaków) w pewnym języku (np. w polskim). Wiadomość zakodowana, czyli szyfrogram, to także ciąg symboli. Podczas naszych rozważań zakładamy, iż szyfrogram jest ciągiem nad tym samym alfabetem co tekst jawny. Przed zakodowaniem nadawca dzieli tekst jawny na tzw. jednostki. Jednostką tekstu jawnego może być pojedynczy symbol, dwójka symboli, itp.. Dopiero jednostkę tekstu jawnego poddaje się procesowi kodowania otrzymując jednostkę szyfrogramu. Kolejne jednostki szyfrogramu mogą być niezależnie wysyłane od nadawcy do odbiorcy. Odbiorca poddaje otrzymany szyfrogram procesowi dekodowania dostając jednostkę tekstu jawnego.
Funkcja kodująca \( f \) to permutacja
\( f:\mathcal{J}\longrightarrow\mathcal{J}, \)
gdzie \( \mathcal{J} \) to zbiór wszystkich, możliwych jednostek tekstu jawnego i szyfrogramu (w skrócie jednostki wiadomości).
Funkcja dekodująca jest permutacją odwrotną do funkcji kodującej. Oznaczamy ją przez \( f^{-1} \), gdzie \( f \) jest odpowiednią funkcją kodującą.
Funkcja kodująca/dekodująca zależy zazwyczaj od parametrów, zwanych kluczami. Przyjmuje się, iż funkcja kodująca (jej wzór, bądź algorytm ją realizujący) jest ogólnie dostępna. Zachowane w tajemnicy są jedynie klucze.
Kryptosystem to para \( (\mathcal{J},f) \), czyli zbiór jednostek wiadomości \( \mathcal{J} \) i funkcja kodująca \( f \).
Pierwszym krokiem do określenia kryptosystemu jest poetykietowanie jednostek wiadomości pewnymi obiektami matematycznymi, na których będzie można określić funkcję kodującą (permutację). W naszych rozważaniach zawsze będą to kolejne liczby naturalne, jednak w ogólności rozważa się w tym miejscu także wektory bądź np. krzywe eliptyczne czy obecnie nawet już hipereliptyczne.
Przykład
Rozważmy alfabet jako zbiór cyfr, polskich liter oraz dodatkowych kilku znaków interpunkcyjnych.
Poetykietujmy symbole alfabetu kolejnymi liczbami naturalnymi.
\( \begin{array} {rrrrrrrrrrrrrrrr} A & Ą & B & C & Ć & D & E & Ę & F & G & H & I & J & K & L & Ł \\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline M & N & Ń & O & Ó & P & R & S & Ś & T & U & W & Y & Z & Ż & Ź \\ 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 \\ \hline & . & ? & ! & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 \end{array} \)
Niech jednostki wiadomości zawierają tylko jeden symbol. Wtedy zbiór jednostek wiadomości to \( \mathbb{Z}_{46}={\{ {0,\ldots,45} \} } \). Podzielmy tekst 'MATEMATYKA DYSKRETNA 2' na jednostki wiadomości. Na podstawie tabeli powyżej kolejne jednostki to:
\( 16,0,25,6,16,0,25,28,13,0,32,5,28,23,13,22,6,25,17,0,32,38. \)
Rozważmy teraz jednostki wiadomości zawierające dwie litery. Wtedy łatwo policzyć, że mamy \( 46\cdot46=2116 \) możliwych jednostek. Ponumerujmy je w sposób naturalny: jednostka \( xy \) otrzymuje numer
\( 46x+y\in{\{ {0,\ldots,2115} \} }. \)
Zatem zbiór jednostek wiadomości to \( \mathbb{Z}_{2116}={\{ {0,\ldots,2115} \} } \). Jak teraz wyglądają jednostki wiadomości 'MATEMATYKA DYSKRETNA 2'?
\( \begin{align*} \textrm{MA} & \equiv & 16\cdot46+0=736, \\ \textrm{TE} & \equiv & 25\cdot46+6=1156, \\ & \ldots & \end{align*} \)
To przykład bardzo prostego systemu kryptograficznego. Są poszlaki świadczące o tym, że Juliusz Cezar używał tej metody do porozumiewania się ze swoimi generałami.
Funkcja kodująca jest tu oparta na dodawaniu modulo rozmiar \( \vert\mathcal{J}\vert \) zbioru jednostek wiadomości:
\( f(P)=(P+b) {\sf mod} \vert \mathcal{J}\vert . \)
Parametr \( b\in{\{ {0,\ldots,\vert\mathcal{J}\vert-1} \} } \) (choć wartość \( 0 \) jest niepraktyczna :)) jest kluczem, który powinien pozostać tajny. Odbiorca otrzymując szyfrogram \( C \) dekoduje go następująco:
\( f^{-1}(C)=(C-b) \ {\sf mod} \vert \mathcal{J}\vert . \)
Zauważmy, że ten sam parametr \( b \) jest kluczem funkcji dekodującej.
Przykład
Zakodujmy w kryptosystemie Cezara wiadomość: `FARSALOS'. Przyjmijmy, iż jednostki wiadomości zawierają jeden symbol. Wtedy, zgodnie z tabelą, numeryczny odpowiednik naszej wiadomości to:
\( 8,0,22,23,0,14,19,23. \)
Jeśli klucz funkcji (de)kodującej to \( b=33 \), to szyfrogram składa się z następujących jednostek:
\( 41,33,9,10,33,1,6,10, \)
czyli `5.GH.EA' jest treścią szyfrogramu.
Wyobraźmy sobie, iż nie jesteśmy nadawcą ani odbiorcą wiadomości, lecz osobą trzecią, bardzo zainteresowaną treścią przesyłanej wiadomości. Jak już wcześniej wspomnieliśmy zakładamy, iż wiadomo jaki kryptosystem jest użyty (w szczególności jaki jest zbiór jednostek wiadomości). Nieznane są jedynie klucze funkcji (de)kodującej.
Kryptoanaliza to dział kryptografii badający możliwość dekodowania wiadomości bez znajomości kluczy użytego kryptosystemu. W ogólności badane są tu też możliwości zamiany wiadomości, fałszowania podpisów, itp..
Załóżmy, iż przechwyciliśmy wiadomość zakodowaną w poprzednim przykładzie. Ponieważ istnieje tylko \( 46 \) możliwych wartości klucza, możemy szybko sprawdzić każdą ewentualność i prawie na pewno tylko w jednym przypadku zdekodowana wiadomość będzie miała sens. Widzimy więc, iż złamanie tego szyfru jest dziecinnie proste.
Jak poprawić bezpieczeństwo kryptosystemu Cezara? Można powiększyć zbiór jednostek wiadomości poprzez zwiększenie liczby symboli alfabetu w jednej jednostce. Wtedy automatycznie będzie więcej możliwych wartości klucza i trudniej będzie je wszystkie przeglądnąć.
Rozwiązanie to jest jednak podatne na tzw. analizę częstotliwości. Wróćmy na chwilę do jednostek wiadomości zawierających jeden symbol. W każdym języku naturalnym pewne symbole występują częściej, np. w języku polskim najczęściej używamy liter: A, E, I, itp. Gdy w przechwyconej wiadomości pewien symbol powtarza się częściej, możemy podejrzewać, iż reprezentuje on jedną z wymienionych liter. W przypadku gdy jednostki wiadomości zawierają więcej symboli analizujemy częstotliwość występowania odpowiednio długich zbitek liter. Jest to skuteczna metoda o ile mamy wystarczająco dużą próbkę zakodowanego tekstu.
Przykład
Przyjmijmy, iż przechwyciliśmy zakodowaną wiadomość: '5.GH.EA' (z poprzedniego przykładu). Wiedząc, iż zakodowana jest ona w kryptosytemie Cezara z jednostką informacji zawierającą pojedynczy symbol dokonując analizy częstotliwości symboli możemy zgadywać, iż symbol '.' (wartość \( 33 \)) reprezentuje symbol o dużej częstotliowści. Zgadując, iż jest to 'A' (wartość \( 0 \)) mamy
\( f('A')='5',\ \textrm{czyli}\ f(0)=0+b {\sf mod} 45 =33,\ \textrm{czyli}\ b=33. \)
Zatem bez sprawdzania wszystkich możliwych wartości udało nam się poznać wartość klucza, a co za tym idzie treść wiadomości
To nieznaczne udoskonalenie kryptosystemu Cezara. Funkcja kodująca jest tym razem, tzw. funkcją afiniczną na zbiorze \( \mathbb{Z}_{\vert J \vert} \), czyli
\( f(P)=a\cdot P+b {\sf mod} \vert\mathcal{J}\vert , \)
gdzie \( a,b\in\mathbb{Z}_{\vert\mathcal{J}\vert} \) są kluczami \( f \) i co bardzo ważne \( a\perp\vert\mathcal{J}\vert \) (dlaczego?). Sprawdźmy, iż po zakodowaniu i zdekodowaniu wrócimy do tego samego elementu
\( \begin{align*} f^{-1}(f(P)) & =f^{-1}(a\cdot P+b {\sf mod} \vert\mathcal{J}\vert ) \\ & =a^{-1}(a\cdot P+b {\sf mod} \vert\mathcal{J}\vert )+a^{-1}b {\sf mod} \vert\mathcal{J}\vert \\ & =a^{-1}(a\cdot P+b)-a^{-1}b {\sf mod} \vert\mathcal{J}\vert \\ & =P+a^{-1}b-a^{-1}b {\sf mod} \vert\mathcal{J}\vert \\ & =P {\sf mod} \vert\mathcal{J}\vert . \end{align*} \)
Pozostawiamy czytelnikowi wypracowanie szybkiego sposobu"złamania" tego kryptosystemu.
Klucz kodowania - \( K_K \) to parametr(y) funkcji kodującej. Znając je można wysyłać zakodowane wiadomości.
Klucz dekodowania - \( K_D \) to paramert(y) funkcji dekodującej. Znając je można dekodować wiadomości.
Przez wieki uważano, że w dowolnym kryptosystemie znajomość klucza kodujacego \( K_K \) pozwala na szybkie poznanie klucza dekodującego znajomość \( K_D \), czyli że każdy kto umie kodować wiadomości może je też dekodować. Tak jest w rozważanym powyżej kryptosystemie Cezara. Jeśli Cezar używał tego samego kryptosystemu do kontaktu ze wszystkimi swoimi generałami, wtedy mogło dochodzić do sytuacji niepożądanych np. gdy generał A wysłał Cezarowi zaszyfrowaną wiadomość, generał B przechwytując kuriera po drodze mógł ją odczytać.
Kryptosystem z kluczem publicznym to system \( (\mathcal{J},f,K_K, K_D) \), gdzie \( K_K \) i \( K_D \) są odpowiednio kluczem kodującym i dekodującym, w którym
Szukamy więc funkcji \( f \) którą w jedną stronę liczy się relatywnie szybko na podstawie znajomości \( K_K \). Natomiast jej odwrotna \( f^{-1} \) jest bardzo trudna do policzenia bez dodatkowej informacji \( K_D \). W sposób naturalny przychodzi tu na myśl problem znajdowania rozkładu na czynniki pierwsze liczb naturalnych. W szczególności: wymnożenie dwu dużych liczb pierwszych jest łatwe (można to zrobić w czasie wielomianowym od długości ich zapisu), natomiast szybkie znalezienie rozkładu na czynniki pierwsze ich iloczynu (bez znajomości wyjściowych liczb lub innych dodatkowych informacji) wydaje się być problemem ekstremalnie trudnym. Właśnie na tym spostrzeżeniu oparta jest idea kryptosystemu RSA.
Nazwa kryptosystemu pochodzi od pierwszych liter nazwisk jego trzech pomysłodawców: Rivest, Shamir i Adelman. Choć jest to jeden z najstarszych kryptosystemów z kluczem publicznym (wynaleziony w 1977 roku) wciąż jest szeroko stosowany w komercyjnych protokołach. Jedynie długości kluczy rosną wraz ze wzrostem mocy obliczeniowej komputerów.
Uwaga: jest to oczekiwany czas działania, a nie maksymalny (pesymistyczny).
Poprawność tego kryptosystemu, czyli że \( f^{-1}(f(P))=P \), dla dowolnego \( P\in\mathbb{Z}_n \) wynika bezpośrednio z następującej obserwacji:
Obserwacja 7.1 [Poprawność RSA]
\( P^{ed}\ \equiv_{n}1 ,\qquad \) dla dowolnego \( P \in \mathbb{Z}_n \).
Dowód
Ponieważ \( ed\ \equiv_{\varphi(n)}1 \) mamy \( ed=a\varphi(n)+1 \) dla pewnego \( a \).
Załóżmy najpierw, ze \( p\perp n \). Wtedy z Twierdzenia Eulera dostajemy \( P^{\varphi(n)}\ \equiv_{n}1 \), a zatem \( P^{ed}=P^{a\varphi(n)+1}\equiv_n P \).
Jeśli zaś \( p\not\perp n \), to \( p|P \) lub \( q|P \). Załóżmy, bez straty ogólności, że \( q|P \), czyli \( P=bq \) dla pewnego \( 0 < b < p \), bo \( bq=P < n=pq \). Na mocy Małego Twierdzenia Fermata mamy:
\( \begin{align*} b^{p-1} & \equiv_p & 1, \\ q^{p-1} & \equiv_p & 1, \end{align*} \)
skąd:
\( \begin{align*} b^{a(p-1)(q-1)} & \equiv_p & 1, \\ q^{a(p-1)(q-1)} & \equiv_p & 1, \end{align*} \)
i dalej
\( \begin{align*} b\cdot(bq)^{a(p-1)(q-1)} & \equiv_p & b \cdot 1 = b. \end{align*} \)
Mnożąc obie strony ostatniej kongruencji przez \( q \) dostajemy
\( \begin{align*} bq\cdot(bq)^{a(p-1)(q-1)} & \equiv_{pq} & bq \end{align*} \)
czyli
\( P^{ed} = (bq)^{a(p-1)(q-1)+1}= (bq)\cdot (bq)^{a(p-1)(q-1)} \equiv_n bq = P, \)
co było do udowodnienia.
Bezpieczeństwo kryptosystemu RSA opiera się na domniemaniu trudności następującego problemu:
Szybkie rozwiązanie problemu faktoryzacji rozwiązałoby problem RSA. Gdyby ktoś znał rozkład \( n \), to znaczy liczby \( p \) i \( q \), miałby także \( \varphi(n)=(p-1)(q-1) \). Wtedy, korzystając z publicznie dostępnego \( e \), obliczyłby rozszerzonym algorytmem Euklidesa \( d \). Dopóki nie jest znany efektywny algorytm rozwiązujący jeden z tych problemów (problem RSA, problem faktoryzacji) kryptosystem RSA pozostaje bezpieczny. Wzrastająca szybkość komputerów zmusza użytkowników RSA do zwiększania długości kluczy. Obecnie stosowane klucze mają najczęściej \( 1024 \) lub \( 2048 \) bitów. Największy złamany klucz (klucz dla którego znaleziono rozkład) ma długość \( 663 \) bity (stan z roku 2005).
W praktyce wiadomość przed zakodowaniem podlega wstępnej obróbce (padding). Zauważmy, że wartości \( 0 \) i \( 1 \) nie podlegają zmianie przy kodowaniu (z własności potęgowania), przez co stanowią one część informacji czytelnej dla wszystkich nawet w szyfrogramie. W praktyce różnymi metodami unika się takich wartości. Rozważania te już jednak wykraczają poza tematykę tego wykładu.
Przykład
Widzieliśmy, że znając rozkład \( n= pq \) można łatwo obliczyć \( \varphi(n) \), a tym samym klucz \( d \) odpowiadający publicznemu kluczowi \( e \). Na odwrót, znając \( n \) oraz \( \varphi(n) \) można szybko rozłozyć liczbę \( n \) na czynniki pierwsze:
a zatem mamy rozwiązać układ równań postaci:
\( \begin{align*} x \cdot y & = a \\ x + y & = 2b \end{align*} \)
skąd \( x,y \) wynoszą \( b \pm \sqrt{b^2-a} \).
Pokazuje to, że wartości funkcji Eulera sa równie trudne do policzenia, jak faktoryzacja liczb.
Uwaga
Kryptosystem RSA wykorzystywany jest poza szyfrowaniem również w wielu innych protokołach kryptograficznych. Na bazie tego systemu można na przykład zbudować podpis elektroniczny. Mimo, że zagadnienia te wykraczają już znacznie poza treść tego wykładu, pokazują one jak wielką rolę odgrywa obecnie teoria liczb w informatyce.
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.