Matematyka dyskretna 2/Wykład 7: Zastosowanie teorii liczb w kryptografii

From Studia Informatyczne

Spis treści

Wstęp

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.

Matematyczny model kodowania i dekodowania

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.


\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 \endarray


Niech jednostki wiadomości zawierają tylko jeden symbol. Wtedy zbiór jednostek wiadomości to \mathbb{Z}_{46}={\left\{ {0,\ldots,45} \right\} }. 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{\left\{ {0,\ldots,2115} \right\} }.


Zatem zbiór jednostek wiadomości to \mathbb{Z}_{2116}={\left\{ {0,\ldots,2115} \right\} }. Jak teraz wyglądają jednostki wiadomości 'MATEMATYKA DYSKRETNA 2'?


\aligned \textrm{MA}&\equiv& 16\cdot46+0=736,\\ \textrm{TE}&\equiv& 25\cdot46+6=1156,\\ &\ldots& \endaligned


Kryptosystem Cezara.

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 \left\vert\mathcal{J}\right\vert zbioru jednostek wiadomości:


f(P)=(P+b) \mbox{ {\sf mod} } \left\vert\mathcal{J}\right\vert .


Parametr b\in{\left\{ {0,\ldots,\left\vert\mathcal{J}\right\vert-1} \right\} } (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) \mbox{ {\sf mod} } \left\vert \mathcal{J}\right\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 \mbox{ {\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

Kryptosystem afiniczny.

To nieznaczne udoskonalenie kryptosystemu Cezara. Funkcja kodująca jest tym razem, tzw. funkcją afiniczną na zbiorze \mathbb{Z}_{\left\vertJ\right\vert}, czyli


f(P)=a\cdot P+b \mbox{ {\sf mod} } \left\vert\mathcal{J}\right\vert ,


gdzie a,b\in\mathbb{Z}_{\left\vert\mathcal{J}\right\vert} są kluczami f i co bardzo ważne a\perp\left\vert\mathcal{J}\right\vert (dlaczego?). Sprawdźmy, iż po zakodowaniu i zdekodowaniu wrócimy do tego samego elementu


\aligned f^{-1}(f(P))&=f^{-1}(a\cdot P+b \mbox{ {\sf mod} } \left\vert\mathcal{J}\right\vert )\\ &=a^{-1}(a\cdot P+b \mbox{ {\sf mod} } \left\vert\mathcal{J}\right\vert )+a^{-1}b \mbox{ {\sf mod} } \left\vert\mathcal{J}\right\vert \\ &=a^{-1}(a\cdot P+b)-a^{-1}b \mbox{ {\sf mod} } \left\vert\mathcal{J}\right\vert \\ &=P+a^{-1}b-a^{-1}b \mbox{ {\sf mod} } \left\vert\mathcal{J}\right\vert \\ &=P \mbox{ {\sf mod} } \left\vert\mathcal{J}\right\vert . \endaligned


Pozostawiamy czytelnikowi wypracowanie szybkiego sposobu"złamania" tego kryptosystemu.

Klucz publiczny. RSA.

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

  • K_K jest powszechnie dostępny; K_D jest zachowywany w tajemnicy,
  • znajomość K_K pozwala na szybkie kodowanie jednostki tekstu, czyli obliczanie f(P) dla P\in\mathcal{J},
  • znajomość K_K nie pozwala (bez znajomości K_D) na szybkie dekodowanie jednostki szyfrogramu, czyli obliczanie f^{-1}(C) dla C\in\mathcal{J},
  • znajomość K_D daje możliwość szybkiego zdekodowania jednostki szyfrogramu.

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.

Kryptosystem 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.

Opis działania RSA:

  • Wybierz losowo dwie bardzo duże różne liczby pierwsze p i q.
    • To jak duże mają być to liczby zależy właśnie od mocy obliczeniowej komputerów. Oczywiście, im większe liczby tym trudniej złamać kod (obliczyć K_D) ale jednocześnie, im większe liczby, tym dłużej trwa proces kodowania i dekodowania wiadomości.
    • To, że liczba ma być wybrana losowo oznacza, że jest uzyskana z pomocą generatora liczb pseudo-losowych. Ale co to oznacza wybrać (pseudo)losowo liczbę pierwszą?
      • Wylosuj odpowiednio dużą liczbę m. Jeśli jest ona parzysta to podstaw m:=m+1.
      • Zaaplikuj testy pierwszości (szczegółowo omówimy je w kolejnej części wykładu) do m. Jeśli okaże się złożona podstaw m:=m+2 i tak aż do znalezienia liczby pierwszej. Z Twierdzenia o Liczbach Pierwszych wiemy, że częstotliwość występowania liczb pierwszych w pobliżu liczby m wynosi \frac{1}{\ln{m}}, a więc możemy oczekiwać że po O(\lg{m}) próbach test pierwszości zwróci wynik pozytywny.
    • Wkrótce przedstawimy test pierwszości działający w czasie O(\lg^{3}m). A więc oczekiwany czas "wylosowania" liczby pierwszej w pobliżu m wynosi O(\lg^4{m}).

Uwaga: jest to oczekiwany czas działania, a nie maksymalny (pesymistyczny).

  • Niech n=p\cdot q. Wtedy \varphi(n)=\varphi(p)\cdot\varphi(q)=(p-1)\cdot(q-1). Wybierz losowo e\in{\left\{ {1,2,3,\ldots,\varphi(n)-1} \right\} } względnie pierwsze z \varphi(n). Niech d\in{\left\{ {1,\ldots,\varphi(n)-1} \right\} } takie, że e\cdot d\ \equiv_{\varphi(n)}1.
    • Podobnie jak wcześniej szukaliśmy losowo liczb pierwszych teraz możemy szukać liczby e. Zamiast aplikować test pierwszości sprawdzamy algorytmem Euklidesa względną pierwszość z \varphi(n) (O(\lg^3{\varphi(n)})). Kiedy uda nam sie trafić (statycznie po O(\log{\varphi(n)}) krokach) rozszerzony algorytm Euklidesa wyznaczy nam d, w czasie O(\log^3{\varphi(n)}).
    • oczekiwany czas działania tego kroku to O(\log^4{n}).
  • Opublikuj klucz publiczny: K_K=(n,e) i zachowaj do własnego użytku klucz dekodujący K_D=(n,d).
  • Zdefiniuj:
    • zbiór jednostek wiadomości jako \mathbb{Z}_n={\left\{ {0,1,\ldots,n-1} \right\} },
    • funkcję kodującą:
      f(P)=P^e \mbox{ {\sf mod} } n ,\qquad dla P \in \mathbb{Z}_n.
    • funkcję dekodującą:
      f^{-1}(C)=C^d \mbox{ {\sf mod} } n ,\qquad dla C \in \mathbb{Z}_n.

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:


\aligned b^{p-1} &\equiv_p& 1,  \\ q^{p-1} &\equiv_p& 1,  \endaligned


skąd:


\aligned b^{a(p-1)(q-1)} &\equiv_p& 1,  \\ q^{a(p-1)(q-1)} &\equiv_p& 1,  \endaligned


i dalej


\aligned b\cdot(bq)^{a(p-1)(q-1)} &\equiv_p& b \cdot 1 = b.  \endaligned


Mnożąc obie strony ostatniej kongruencji przez q dostajemy


\aligned bq\cdot(bq)^{a(p-1)(q-1)} &\equiv_{pq}&  bq  \endaligned


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.

image:End_of_proof.gif

Bezpieczeństwo RSA.

Bezpieczeństwo kryptosystemu RSA opiera się na domniemaniu trudności następującego problemu:

  • Problem RSA: znajdź e-ty pierwiastek liczby C\in\mathbb{Z}_n modulo n, a więc posiadając e,n oraz C znajdź takie P, że P^e\ \equiv_{n}C. Oczywiście, rozwiązanie tego problemu jest równoważne złamaniu RSA. Jednak wydaje się, że jest to równie trudny problem jak problem faktoryzacji (choć nie zostało to udowodnione).

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:

  • znamy bowiem iloczyn szukanych czynników p \cdot q = n
  • oraz sumę tych czynników p+q = n+1 -\varphi(n)

a zatem mamy rozwiązać układ równań postaci:


\aligned x \cdot y &= a \\ x + y &= 2b \endaligned


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.

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,\ldots,\left\lfloor \sqrt{m}\right\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:

  • Wybierz losowe a\in{\left\{ {0,1,2,\ldots,n-1} \right\} }.
  • 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\in{\left\{ {1,2,\ldots,n-1} \right\} } 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:

  • 1\leq b< n,
  • b\perp n,
  • b^{n-1}\ \equiv_{n}1.

Przykład

Liczba 91=7\cdot13 jest pseudopierwsza przy podstawie 3.

  • 3\perp91,
  • \varphi(91)=\varphi(7)\cdot\varphi(13)=6\cdot12=72,
  • z Twierdzenia Eulera mamy 3^{90}\equiv_{91}3^{1\cdot71+18}\equiv_{91}3^{18},
  • liczymy 3^{18} \mbox{ {\sf mod} } 91 metodą szybkiego potęgowania:
    • 18=(10010)_2,
    • 3^2= 9,
    • 3^4=9\cdot9=81,
    • 3^8=81\cdot81=6561\equiv_{91}9,
    • 3^{16}\equiv_{91}9\cdot9=81.
  • 3^{18}=3^{16}\cdot3^2\equiv_{91} 81\cdot 9=729\equiv_{91} 1.

Zatem 3^{90}\ \equiv_{91}1, czyli 91 jest pseudopierwsze przy podstawie 3.

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

  • 2\perp91 a zatem znów z Twierdzenia Eulera 2^{90}\equiv_{91}2^{18},
  • liczymy 2^{18} \mbox{ {\sf mod} } 91 metodą szybkiego potęgowania:
    • 18=(10010)_2,
    • 2^2= 4,
    • 2^4=4\cdot4=16,
    • 2^8=16\cdot16=256\equiv_{91}74,
    • 2^{16}\equiv_{91}74\cdot74=5476\equiv_{91}16.
  • 2^{18}=2^{16}\cdot2^2\equiv_{91} 16\cdot 2=32.

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:

  • 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{\left\{ {1,\ldots,n-1} \right\} } 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 {\left\{ {b_1,\ldots,b_m} \right\} } 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.

image:End_of_proof.gif

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{\left\{ {1,2,\ldots,n-1} \right\} }.
  • Sprawdź algorytmem Euklidesa (O(\lg^3{n})) czy d=\mbox{\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{\left\{ {1,\ldots,n-1} \right\} } 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 \mbox{\sf NWD}(p^2,n')=1 i z Chińskiego Twierdzenia o Resztach wiemy, iż istnieje b takie, że


\aligned b&\equiv_{p^2}&g,\\ b&\equiv_{n'}&1. \endaligned


W szczególności


\mbox{\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\nmid n-1. Ponieważ p^2\nmid 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


\aligned b&\equiv_{p}&g,\\ b&\equiv_{\frac{n}{p}}&1. \endaligned


Oczywiście \mbox{\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\nmid 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.

image:End_of_proof.gif

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ść.

image:End_of_proof.gif

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} \mbox{ {\sf mod} } n ,\quad b^{(n-1)/4} \mbox{ {\sf mod} } n , \quad \ldots \quad b^{(n-1)/2^s} \mbox{ {\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.

image:End_of_proof.gif

W praktyce ciąg ten analizowany jest z drugiej strony. Niech n-1=2^st, gdzie t jest nieparzysta. Najpierw obliczamy b^t \mbox{ {\sf mod} } n później (jeśli otrzymaliśmy coś różnego jest od 1) obliczamy b^{2t} \mbox{ {\sf mod} } n, później b^{4t} \mbox{ {\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{\left\{ {1,2,\ldots,n-1} \right\} }. 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{\left\{ {2,\ldots,n-1} \right\} },
  • Oblicz b^t \mbox{ {\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} \mbox{ {\sf mod} } n ,2^{2^2t} \mbox{ {\sf mod} } n ,2^{2^3t} \mbox{ {\sf mod} } n ,\ldots,2^{2^{s-1}t} \mbox{ {\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} \mbox{ {\sf mod} } n ,2^{2^2t} \mbox{ {\sf mod} } n ,2^{2^3t} \mbox{ {\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{\left\{ {1,\ldots,n-1} \right\} }.

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.