Wprowadzenie do Teorii Algorytmów
(Introduction to Algorithms Theory)
Prof. Dr hab. Alexander Prokopenya
Szkoła Główna Gospodarstwa Wiejskiego w Warszawie
Katedra Zastosowań Informatyki
Wykład 2-3. Algorytmy na liczbach
Teorię liczb traktowano niegdyś jako piękny, ale kompletnie bezużyteczny dział
czystej matematyki. Obecnie algorytmy teorioliczbowe znajdują szerokie zastosowanie
dzięki wynalezieniu systemów kryptograficznych bazujących na dużych liczbach pierw-
szych. Możliwość praktycznego stosowania tych systemów opiera się na tym, że umiemy
łatwo znajdować duże liczby pierwsze, natomiast ich bezpieczeństwo wynika z tego, iż nie
potrafimy rozłożyć na czynniki iloczynu dużych liczb pierwszych. W tym wykładzie
przedstawimy nieco wiadomości z teorii liczb i przegląd algorytmów dla różnorodnych
problemów obliczeniowych związanych z liczbami.
Rozmiar danych wejściowych będziemy określać liczbą bitów potrzebnych dla re-
presentowania tych danych. Dla liczby N ł� 0 ilość bitów można określić ze wzoru
=� 4 bitów,
��log( N +�1)ł�, na przykład dla representacji liczby N =� 8 jest potrzebne ��log9ł�
gdzie mamy na myśli log N �� log2 N . Przy podstawie b za pomocą k cyfr można wyrazić
liczby aż do bk -�1; na przykład, dziesiętnie przy użyciu trzech cyfr daje się wyrazić
wszystko aż do 999 =� 103 -�1. Przy zmianie podstawy z b na a ilość cyfr potrzebnych dla
representowania liczby całkowitej N zmienia się zgodnie z regułą
logb(N +�1) =� loga(N +�1) / loga b. Zatem rozmiar liczby całkowitej N przy podstawie a to jej
rozmiar przy podstawie b pomnożony przez stały czynnik loga b . Czyli w notacji dużego
O podstawa nie gra roli, a rozmiar liczby zapisujemy po prostu jako O(log N) .
1. Podstawowa arytmetyka
1.1. Dodawanie. Zaczniemy od podstawowej arytmetyki, stanowiącej najbardziej odpowiedni
punkt wyjścia, gdyż, jak wiadomo, słowem algorytmy nazywano początkowo jedynie metody
rozwiązywania problemów obliczeniowych związanych z liczbami. Najpierw przyjrzymy się
metody dodawania i przemyślim się, dlaczego ona dziala.
Podstawową własnością liczb dziesiętnych jest, że suma dowolnych trzech jednocyfro-
wych liczb jest co najwyżej dwucyfrowa. Szybkie sprawdzenie: suma ta wynosi co najwyżej
9 +� 9 +� 9 =� 27 , które jest dwucyfrowe. Reguła jest prawdziwa nie tylko dla liczb dziesiętnych,
lecz także dla liczb przy dowolnej podstawie b ł� 2 . W systemie binarnym, na przykład, maksy-
malna możliwa suma trzech liczb wynosi 3, które jest liczbą 2-bitową.
Przy użyciu tej prostej reguły możemy dodać dwie liczby przy dowolnej podstawie: nale-
ży wyrównać liczby do prawej strony, a następnie wykonać jeden przebieg od prawej do lewej,
cyfra po cyfrze, obliczając sumę, a nadmiar przenosząc dalej. Ponieważ wiemy, że każda taka
suma jest liczbą dwucyfrową, przeniesienie składa się zawsze a jednej cyfry, a więc w każdym
kroku dodajemy trzy liczby jednocyfrowe.
1
Przykład. Suma dwuch liczb n-cyfrowych przy podstawie B.
K� pierwsza liczba
an-�1 a1 a0
K� druga liczba
bn-�1 b1 b0
K� 0 przeniesienie
cn cn-�1 c1
K� suma
sn sn-�1 s1 s0
Początkowo przeniesienie c0 =� 0. Dalej ai +� bi +� ci =� ci+�1 �� B +� si dla 0 Ł� i <� n i sn =� cn .
Dla sumy liczb binarnych 23+�18 =� 41, na przykład, mamy
1 0 1 1 1 (23)
1 0 0 1 0 (18)
1 0 1 1 0 0 (c)
1 0 1 0 0 1 (41)
Odpowiedni algorytm można zapisać w postaci:
Addition(a,b)
1 c :=� 0
2 for i := 0 to n-1 do
3
dodaj ai , bi i ci i znajdz sumę si przeniesienie ci+�1 od
4
sn :=� c
Dla oszacowania czasu działania algorytmu założmy, że a oraz b mają po n bitów każda.
Wówczas suma a i b ma co najwyżej n +�1 bitów, a każdy bit tej sumy jest liczony w stalym cza-
sie. Całkowity czas działania algorytmu dodawania jest zatem postaci t0 +� t1n , gdzie t0 i t1 są
pewnymi stałymi; innymi słowy jest on liniowy. Zamiast martwić się o dokładne wartości t0 i
t1 , pominiemy szczególy i oznaczymy czas działania jako O(n) .
Czy istnieje szybszy algorytm? Dla dodawania odpowiedz
jest prosta: żeby dodać dwie n-
bitowe liczby, musimy przynajmniej je przeczytać i zapisać wynik, a to wymaga przecież n ope-
racji. Dlatego ten algorytm dodawania jest optymalny, z dokładnościaą do stałych współczynni-
ków.
1.2. Mnożenie i dzielenie. Podstawową własnością liczb całkowitych jest, że iloczyn dowolnych
dwóch jednocyfrowych liczb jest co najwyżej liczbą dwucyfrowa. Szybkie sprawdzenie: w sys-
temie dziesiętnym iloczyn dwóch takich liczb wynosi co najwyżej 9��9 =� 81, które jest dwucy-
frowe. Przy podstawie B iloczyn dwóch cyfr wynosi co najwyżej
(B -�1)2 =� B2 -� 2B +�1 =� (B -� 2)�� B1 +�1�� B0 <� (B -�1)�� B1 +� (B -�1)�� B0 ,
które jest dwucyfrowe.
Znany ze szkoły podstawowej algorytm mnożenia dwóch liczb a i b polega na utworze-
niu tablicy sum pośrednich, z których każda representuje iloczyn a przez jedną z cyfr b, na przy-
kład, a ��bj , j =� 0,1,...,n -�1. Dla dowolnej cyfry ai liczby a iloczyn ai ��bj jest liczba dwucyfro-
wa
ai ��bj =� ci �� B +� di , i =� 0,1,...,n -�1.
Rezultat mnożenia a ��bj otrzymujemy po dodawaniu liczb c =� (cn-�1...c00) i d =� (dn-�1...d0) ,
gdzie liczba c ma zero z prawej strony in dlatego jest (n +�1) -cyfrowa:
2
cn-�1 cn-�2 L� ci ci-�1 L� c0 0
dn-�1 L� di+�1 di L� d1 d0
(an-�1K�ai K�a0)��bj �� .
pi,n pi,n-�1 L� L� L� L� pi,1 pi,0
Dla każdego i mamy jedno mnożenie bitów, co wymaga n operacji mnożenia. Dalej dodawanie
dwuch (n +�1) -cyfrowych liczb potrzebuje (n +�1) operacje dodawania bitów, razem
2n +�1 =� O(n) podstawowe operacje.
Dalej sumy pośrednie są odpowiednio przesuwane w lewo i następnie dodawane.
p0,n p0,n-�1 L� p0,2 p0,1 p0,0
p1,n p1,n-�1 p1,n-�2 L� p1,1 p1,0
p2,n p2,n-�1 p2,n-�2 p2,n-�3 L� p2,0
L�
pn-�1,n L� pn-�1,3 pn-�1,2 pn-�1,1 pn-�1,0
sum of the n partial products
Założmy na przykład, że chcemy pomnożyć 11��10 , w notacji binarnej a =� 1011 i
b =� 1010 . Mnożenie wygląda następująco:
1 0 1 1
1 0 1 0
0 0 0 0
1 0 1 1
0 0 0 0
1 0 1 1
1 1 0 1 1 1 0
W systemie binarnym jest to szczególnie proste, gdyż każda suma częściowa jest albo zerem al-
bo samym a przesuniętym odpowiednio w lewo.
Algorytm mnożenia liczb całkowitych a i b można zapisać w postaci:
Product(a,b)
1 p :=� 0
2 for i := 0 to n-1 do
3
p :=� p +� a ��bi �� Bi od
Jeżeli a i b są liczby n-bitowe, to mamy n sum pośrednich o długościach nie przekracza-
jących 2n bitów (biorąc pod uwagę przesunięcie). Całkowity czas potrzebny, aby dodać wyniki
pośrednie, dodając dwie liczby na raz, wynosi
O(4�4�O(n) O(3� .
n
1�n) +� 4�2�+�...+�4�4�)
4� 4�4�
n-�1 razy
Daje to O(n2) , kwadratowo względem rozmiaru danych wejściowych: wciąż wielomianowo, ale
dużo wolniej niż dodawanie.
Jednak istnieje inny sposób mnożenia, metodę używaną dziś w niektórych krajach Euro-
py. Aby pomnożyć dwie liczby x i y, należy napisać je obok siebie, jak w przykładzie poniżej.
Następnie trzeba powtóżyć następujące czynności: podzelić pierwszą liczbę przez 2, zaokrągla-
jąc wynik w dół ( to znaczy opuścić końcówkę 0,5, jeśli liczba była nieparzysta), oraz podwoić
drugą liczbę. Należy powtarzać te czynności do momentu, aż pierwsza liczba zamaleje do 1.
3
Wówczas trzeba wykreślić wszystkie wiersze, w których pierwsza liczba jest parzysta, oraz do-
dać liczby w drugiej kolomnie, który pozostały.
11 13
5 26
2 52 (wykreslic)
1 104
143 (wynik )
Jeśli jednak teraz porównamy te dwa algorytmy, mnożenie binarne oraz mnożenie przez
połowienie pierwszego czynnika, to zauważymy, że robią one to samo. Trzy liczby dodawane w
drugim algorytmie są dokładnie iloczynami liczby 13 przez potęgi 2 dodawanymi w mietodzie
binarnej. Tutaj liczba 11 nie jest podobna binarnie wprost i musieliśmy wydoby jej binarną po-
stać poprzez sprawdzanie parzystości liczb otrzymanych z niej przez sukcesywne dzielenie przez
2. Ten algorytm znany jako algorytm Al Khwarizmiego jest fascynującym połączeniem systemu
dziesiętnego i binarnego.
Ten algorytm można zatem opisać na różne sposoby. Aby pokazać tę różnorodność, po-
damy trzecią postać  algorytm rekurencyjny, w którym stosujemy regulę
2(x �� / 2 dla y parzystego
��
��y ��)
x �� y =�
��x +� 2(x�� / 2 dla y nieparzystego
��y ��)
��
Odpowiedni algorytm można zapisać w postaci:
funkcja multiply(x, y)
// wejście: dwie n-bitowe liczby całkowite x i y, y ł� 0
// wyjście: ich iloczyn
z:= 0
if y =� 0 then return z
z := multiply(x, / 2
��y ��)
if y jest parzyste then
z :=� 2z
else
z :=� x +� 2z
Czy można to zrobić lepiej? Intuicyjne wydaje się, że mnożenie wymaga dodania około n
wielokrotności jednej z liczb na wejściu, a wiemy, że każde dodawanie jest liniowe, wynikałoby
więc stąd, że potrzebujemy przynajmniej n2 operacji bitowych. Zdumiewające jest zatem to, co
potrzfimy mnożyć znacznie szybczej.
Podzielenie liczby x przez drugą liczbę y ą� 0 oznacza znalezenie ilorazu q oraz reszty r,
gdzie x =� y ��q +� r i 0 Ł� r <� y .
Rekurencyjna wercja dzielenia:
��
ć�
��x / 2����
2�� �� dla x parzystego
��
�� ��
y
x ��
Ł� ł�
=�
��
y ć�
��x ����
��1 +� 2�� / 2 �� dla x nieparzystego
�� ��
��
y y
Ł� ł�
��
Algorytm rekurencyjny dzielenia:
funkcja divide(x, y)
// wejście: dwie n-bitowe liczby całkowite x i y, y ł� 1
4
 // wyjście: ich iloraz oraz reszta z dzilenia x przez y
if x =� 0 then return (q,r) :=� (0,0) fi
(q,r) :=� divide( / 2 y )
��x ��,
q :=� 2q , r :=� 2r
if x jest nieparzyste then r :=� r +�1 fi
if r ł� y then r :=� r -� y , q :=� q +�1 fi
return (q,r)
Podobnie jak mnożenie, metoda ta działa w czasie kwadratowym.
1.3. Arytmetyka modularna. Arytmetyka modularna jest narzędziem do wykonywania dzialań
na liczbach całkowitych o ograniczonym zakresie. Definiujemy x modulo N jako resztę z dziele-
nia x przez N; to znaczy, jeśli x =� q�� N +� r dla 0 Ł� r <� N , to x modulo N jest równe r. Dzieńki
temu możemy mówić o równoważności liczb: x i y przystają modulo N, jeśli różnią się o wielo-
krotność N, symbolicznie
x �� y(mod N) �� N dzieli (x -� y) .
Na przykład, 253 �� 13(mod60) , ponieważ 253-�13 jest wielokrotnością 60. Liczby te mogą
również być ujemne, na przykład 59 �� -�1(mod60) .
Możemy myśleć o arytmetyce modularnej jako o narzędziu ograniczającym liczby do
pewnego ustalonego zbioru {0,1,..., N -�1}, a kiedy próbujemy wyjść poza ten przedział, wracamy
do początku.
W innej interpretacji arytmetyki modularnej działania są wykonywane na wszystkich
liczbach całkowitych, ale cały ich zbiór jest dzielony na N klas równoważności, z której każda
jest postaci {i +� kN;k �� Z�} dla pewnego i między 0 a N -�1. Na przykład, są trzy klasy równo-
ważności modulo 3:
L� -� 9 -� 6 -� 3 0 3 6 9 L�
L� -�8 -� 5 -� 2 1 4 7 10 L�
L� -� 7 -� 4 -�1 2 5 8 11 L�
Każdy element klasy równoważności możemy podstawić za inny; licząc modulo 3, między licz-
bami 5 i 11 nie ma różnicy. Przy takich podstawieniach, dodawanie i mnożenie pozostają dobrze
zdefiniowane:
Reguła podstawiania. Jeśli x �� x'(mod N) i y �� y'(mod N) , to
x +� y �� x'+�y'(mod N) oraz xy �� x' y'(mod N).
Nie jest trudno sprawdzić, że w arytmetyce madularnej własności łączności, przemienności i
rozdzielności dodawania i mnożenia wciąż zachodzą, na przykład,
x +� (y +� z) �� (x +� y) +� z(mod N) łączność
xy �� yx(mod N) przemienność
x(y +� z) �� xy +� xz(mod N) rozdzielność
Biorąc pod uwage także regułę podstawienia, wynika stąd, że wykonując ciąg operacji
arytmetycznych, można w każdym kroku redukować wyniki pośrednie do ich reszt modulo N.
Takie uproszczenie może być znaczącą pomocą przy olbrzymich obliczeniach. Na przykład,
69
2345 �� (�25)� �� 3269 �� 169 �� 1(mod31) ,
99
2596 �� 22 ��(�26)� �� 4��6499 �� 4��199 �� 4(mod63) .
5
1.3.1. Dodawanie i mnożenie modularne.
Aby dodać dwie liczby a i b modulo N, najpierw dodajemy je zwyczajne. Ponieważ a i b są w
zakresie od 0 do N -�1, ich suma jest między 0 i 2(N -�1) . Jeśli ta suma przekracza N -�1, po
prostu musimy odjąć N, aby była z powrotem w wymaganym zakresie. Cale obliczenie sprowa-
dza się więc do dodawania i być może odejmowania liczb nie większych niż 2N . Jego czas
działania jest liniowy od wielkości liczb, innymi słowy O(n) , gdzie n =� N
��log ł� jest rozmiarem
N.
Mnożenie dwóch liczb a i b modulo N znów zaczynamy od zwykłego mnożenia, reduku-
jąc potem wynik modulo N. Iloczyn jest nie większy niż (N -�1)2 , ale wciąż jest to co najwyżej
2n bitów, gdyż log( N -�1)2 =� 2log( N -�1) Ł� 2n . Aby zredukować wynik modulo N, obliczamy
resztę z dzielenia przez N, używając naszego algorytmu dzielenia działającego w czasie kwadra-
towym. Mnożenie modulo pozostaje więc operacją wykonywaną w czasie kwadratowym.
Dzielenie nie jest tak proste. W zwykłej arytmetyce mamy tylko jeden specjalny przypa-
dek  dzielenie przez zero. Okazuje się, że w arytmetyce modularnej potencjalnie mamy więcej
takich przypadków, które opiszemy pózniej. Jednakże, gdzie tylko dzielenie jest dozwolone, mo-
że być wykonane w czasie sześciennym, O(n3) .
1.3.2. Potęgowanie modularne
W kryptosystemach konieczne jest oblicznie xy mod N dla liczb x, y oraz N mających po kilka-
set bitów. Czy można to zrobić szybko?
Aby zapewnić, że liczby, na których wykonujemy obliczenia, nie rosną za bardzo, musi-
my wszystkie pośrednie działania wykonywać modulo N. Pomysl jest następujący: oblicz
xy mod N , mnożąc po kolei przez x modulo N. Otrzymujemy ciąg iloczynów częściowych,
x mod N �� x2 mod N �� x3 mod N �� x4 mod N ��L�� xy mod N ,
który sklada się z liczb mniejszych od N, a poszczególne mnożenia nie trwają zbyt długo. Jest
jednak problem: jeśli y ma 500 bitów, musimy wykonać y -�1 � 2500 mnożeń. Jest jasne, że ten
algorytm jest wykładniczy od rozmiary y.
Na szczęście potrafimy obliczenia te wykonać lepiej: zaczynając od x i obliczjąc kolejno
kwadraty modulo N, otrzymamy
��log y��
x mod N �� x2 mod N �� x4 mod N �� x8 mod N ��L�� x2 mod N .
Każde podniesienie do kwadratu zajmuje tylko O(log2 N) czasu, a w tym przypadku mamy tyl-
ko log y mnożeń. Aby obliczyć xy mod N , po prostu wymnażamy odpowiedni podzbiór tych
potęg  tych, które odpowiadają bitom1 w binarnej representacji y. Na prykład,
x25 =� x110012 =� x100002 �� x10002 �� x12 =� x16 �� x8 �� x1 .
Możemy podać ten pomysł w szczególnie prostej postaci: rekurencyjnego algorytmu, który dzia-
ła, korzystając modulo N z oczywistego wzoru:
2
��
�� (�x��y / 2��)� , gdy y jest parzyste
xy =�
��
2
/ 2
��
)�
��x ��(�x��y �� , gdy y jest nieparzyste
Odpowiedni algorytm rekurencyjny można zapisać w postaći
funkcja modexp(x, y,N)
// wejście: dwie n-bitowe liczby całkowite x oraz N, wykładnik całkowity y
// wyjście: xy mod N
6
if y =� 0 then return 1 fi
z :=� modexp(x, / 2 N )
��y ��,
if y jest parzyste then return z2 mod N
else return x�� z2 mod N fi
Niech n oznacza rozmiar w bitach liczb x, y i N (którakolwiek jest największa). Podobnie jak
przy mnożeniu algorytm ten zatrzyma się po co najwyżej n wywołaniach rekurencyjnych, a pod-
czas każdego wywołania mnoży liczby n-bitowe (ratuje nas tu wykonanie obliczeń modulo N),
zatem całkowity czas działania to O(n3) .
Wykorzystując pseudojęzyk, algorytm można też zapisać w postaci:
funkcja modexp(x, y,N)
f:=1; z:= x
if y =� 0 then return f fi
while y ą� 0 do
if (y mod 2) ą� 0 then f := (f*z mod N) fi
y := y div 2
z := (z*z mod N)
od
return f
1.3.3. Algorytm Euklidesa dla największego wspólnego dzielnika
Definicja. Największą liczbę całkowitą, która dzieli obie liczby całkowite a i b, zwana ich naj-
większym wspólnym dzielnikiem (gcd od ang. greatest common divisor).
Twierdzenie 1. Jeśli a i b są dowolnymi liczbami całkowitymi, nie równymi jednocześnie zeru,
to gcd( a,b) jest najmniejszym dodatnim elementem zbioru {ax +� by : x, y ��Z} kombinacji li-
niowych a i b.
Dowód. Niech s =� ax +� by będzie taką najmniejszą dodatnią kombilacją liniową a i b dla pew-
nych x, y ��Z . Niech q =� / s
��a ��. Wtedy
a mod s = a -� qs =� a -� q(ax +� by) =� a(1-� qx) +� b(-�qy)
także jest kombinacją liniową a i b. Ponieważ jednak a mod s < s, zatem musi być a mod s = 0,
bo s jest najmniejszą dodatnią kombilacją liniową. Zatem s | a i, analogicznie, s | b , więc s jest
wspólnym dzielnikiem a i b, czyli gcd(a,b) ł� s . Z drugiej strony, gcd( a,b) | a i gcd(a,b) | b ,
czyli gcd(a,b) | (ax +� by) =� s . Ponieważ s >� 0 , z tego wynuka gcd(a,b) Ł� s . Skoro gcd(a,b) ł� s
oraz gcd(a,b) Ł� s , to gcd(a,b) =� s i liczba s jest największym wspólnym dzielnikiem a i b.
Mając dwie liczby całkowite x i y, algorytm ten znajduje największy wspólny dzielnik
gcd( x, y).
Reguła Euklidesa. Jeśli x i y są liczbami całkowitymi dodatnimi i x ł� y , to
gcd( x, y) =� gcd( xmod y, y) .
Dowód I. Wystarczy pokazać nieco prostszą regułę, gcd( x, y) =� gcd( x -� y, y), z której powyższą
można uzyskać, odejmując y tyle razy, ile potrzeba.
Jeśli gcd( x, y) =� d , to x =� nd i y =� md , gdzie liczby całkowite n i m są względnie
pierwsze. Zauważmy, że liczby n -� m i m są też względnie pierwsze. Wtedy x -� y =� (n -� m)d i
gcd( x, y) =� gcd( x -� y, y).
Dowód II. Można latwo udowodnić, że jeśli x | y i y | x , to x =� ą�y . Pokażemy, że gcd( x, y) i
gcd( x mod y, y) dzielą się nawzajem.
7
 Najpierw pokażemy, że gcd( x, y) | gcd( x mod y, y) . Jeśli d =� gcd( x, y) , to d | x , d | y i
musi dzielić
x mod y =� x -� y / y =�1�� x +� / y y
��x �� ��x ����
ich kombinacją liniową. Zatem, ponieważ d | y i d | (x mod y), na mocy Twierdzenia 1
d | gcd( y, x mod y) =� ay +� b��(x mod y) dla pewnych a i b.
Dowód, że gcd( x mod y, y) | gcd( x, y) jest prawie identyczny. Jeśli teraz
d =� gcd( x mod y, y), to d | y i d | (x mod y). Ponieważ x =� y �� / y
��x ��+�1��(x mod y) , więc x jest
kombinacją loniową y i (x mod y) i wtedy d | x . Na mocy Twierdzenia 1
d | a �� x +� b�� y =� gcd( x, y) dla pewnych a i b lub gcd( x mod y, y) | gcd( x, y) . Wtedy
gcd( x mod y, y) =� gcd( x, y) .
Stosując regułę Euklidesa, możemy napisać eleganski algorytm rekurencyjny, a jego po-
prawność wynika natychmiast z tej reguly.
funkcja Euclid(a, b)
// wejście: dwie liczby całkowite a i b, a ł� b ł� 0
// wyjście: gcd( a,b)
if b =� 0 then return a fi
return Euclid( b,a modb )
Algorytm Euklidesa możemy też zapisać w postaci iteracyjnej:
funkcja Euclid(a, b)
// wejście: dwie liczby całkowite a i b, a ł� b ł� 0 ; wyjście: gcd( a,b)
if b =� 0 then return a fi
while b ą� 0 do c :=� a modb ; a :=� b ; b :=� c od
return a
Aby dowiedzieć się, jaki jest jego czas działania, musimy zrozumieć, jak szybko argu-
menty (a,b) maleją w każdym kolejnym wywołaniu rekurencyjnym. W jednym wywolaniu re-
kurencyjnym argumenty (a,b) przyjmją wartości (b,a modb): ich kolejność zostaje zmieniona,
a większy z nich, a, redukuje się do a modb . Jest to istotna redukcja.
Lemat. Jeżeli a ł� b, to amodb <� a / 2 .
Dowód. Mamy albo b Ł� a / 2 albo b >� a / 2.W pierwszym przypadku amodb <� b <� a / 2,
a w drugim  amodb =� a -�b <� a / 2.
Znaczy to, że po dwóch kolejnych wywolaniach rekurencyjnych wartości obu argumen-
tów, a i b, są co najmniej dwa razy mniejsze  długość każdego zmniejsza się o co najmniej 1
bit. Jeśli początkowo miały n bitów, to po 2n wywolaniach rekurencyjnych osiągniemy przypa-
dek bazowy. Ponieważ za każdym razem jest wykonywane dzielenie w czasie kwadratowym,
całkowity czas działania to O(n3) .
1.3.4. Rozszerzenie algorytmu Euklidesa
Niech d dzieli a i b. Jak sprawdzić, że d jest największym wspólnym dzielnikiem? Oto test, któ-
rego można użyć, jeśli d jest w odpowiedniej postaci.
Lemat. Jeżeli d dzieli a i b oraz d =� ax +� by dla pewnych liczb całkowitych x i y, to wówczas
d =� gcd(a,b) .
Dowód. Z pierwszych dwóch warunków otrzymujemy, że d jest wspólnym dzielnikiem a i b,
więc nie może być większe niż największy wspólny dzielnik; to znaczy d Ł� gcd(a,b) . Z drugiej
8
strony, ponieważ gcd(a,b) jest wspólnym dzielnikiem a i b, musi również dzielić d =� ax +� by ,
skąd wynika, że gcd(a,b) Ł� d . Obie nierówności implikują d =� gcd(a,b) .
Zauważmy, że x i y mogą być równe 0 lub ujemne. Zatem, jeśli potrafimy wskazać dwie
liczby x i y takie, że d =� ax +� by , to możemy być pewni, że d =� gcd(a,b) . Ale kiedy potrafimy
znalezć takie liczby, w jakich okolicznościach gcd( a,b) można przedstawić w tej weryfikowa-
nej postaci? Okazuje się, że zawsze można. Nawet lepiej, można znalezć współczynniki x i y za
pomocą małego rozszerzenia algorytma Euklidesa.
funkcja extended-Euclid(a, b)
// wejście: dwie liczby całkowite a i b, a ł� b ł� 0
// wyjście: liczby całkowite x,y,d, takie, że d =� gcd(a,b) i ax +� by =� d
if b =� 0 then return (1,0,a) fi
(x', y',d) :=� extended-Euclid(b,a modb )
return ( y', x'-� / b )
��a ��y',d
Lemat. Dla dowolnych dodatnich liczb całkowitych a i b, rozszerzony algorytm Euklidesa
zwraca liczby całkowite x, y i d takie, że gcd(a,b) =� d =� ax +� by .
Dowód. Procedura extended-Euclid(a, b) jest rozszeżeniem procerury Euclid(a, b).
Pierwszy jej wiersz odpowiada testowi  b =� 0 i jest taki samy jak wiersz pierwszy procedury
Euclid. Jeśli b =� 0, to extended-Euclid zwraca nie tylko d =� a , lecz także współczynni-
ki x =�1 oraz y =� 0, takie że a =� ax +� by . Jeśli b ą� 0, extended-Euclid oblicza najpierw
trójkę (x', y',d') taką, że d'=� gcd(b,a mod b) oraz
d'=� b�� x'+�(a mod b)�� y'.
Tak jak w procedurze Euclid, w tym przypadku d =� gcd(a, b) =� d'=� gcd(b,a mod b) . Żeby
znalez
ć x i y takie, że d =� ax +� by , przepiszemy powyższe równanie, korzystając z tego, że
d =� d' i pisząc (a mod b) jako (a -� / b :
��a ��b)
d =� gcd(a, b) =� gcd(b,a mod b) =� bx'+�(a mod b)y'=� bx'+�(a -� / b
��a ��b)y'=�
=� ay'+�b(x'-� / b .
��a ��y')
Jeśli zatem wez
miemy x =� y' , y =� x'-� / b , równanie d =� ax +� by będzie spełnione, co do-
��a ��y'
wodzi poprawność algorytmu dla danych wejściowych (a,b) .
Ponieważ liczba wywołań rekurencyjnych wykonywanych prze procedury Euclid i
extended-Euclid jest jest identyczna, czsy działania tych algorytmów są takie same, z do-
kladnością do stalego czynnika.
Przykład. Licząc gcd(357, 315) , otrzymujemy dwie pierwszych kolomny tablicy
a b d x y
��a / b��
357 315 1 21 -7 8
315 42 7 21 1 -7
42 21 2 21 0 1
21 0 - 21 1 0
Aby znaliez
ć x i y takie, że 357x +� 315y =� 21, zaczynamy od wartości x i y z ostatniego wiersa
i liczymy x i y dla przedostatniego wiersza
x =� y'=� 0, y =� x'-� / b
��a ��y'=�1-� 2��0 =�1.
Zatem
x =� y'=�1, y =� x'-� / b 0 -� 7��1=� -�7 .
��a ��y'=�
9
x =� y'=� -�7 , y =� x'-� / b
��a ��y'=�1-�1��(-�7) =� 8.
Skończyliśmy: -� 7��357 +� 8��315 =� 21, zatem x =� -�7 , y =� 8 .
1.3.5. Dzielenie modularne
W arytmetyce na liczbach rzeczywistych każda liczba a ą� 0 ma odwrotność, 1/ a , a dzielenie
przez a jest tylko mnożenie przez jej odwrotność. W arytmetyce modularnej możemy przyjąć
podobną definicję.
Definicja. Mówimy, że x jest odwrotnością a modulo N, jeśli ax ��1 (mod N) .
Istnieje co najwyżej jedna taka liczba x modulo N i będziemy ją oznaczać przez a-�1. Taka od-
wrotność jednakże nie zawsze istnieje! Na przykład, 2 nie jest odwracalne modulo 6, to znaczy
2x ą�1 (mod 6) dla każdego możliwego wyboru x. W tym przypadku liczby a i N są obie parzy-
ste, a więc (a mod N) jest parzyste, gdyż a mod N =� a -� kN dla pewnego k. Ogólnej, możemy
być pewni, że gcd( a, N) dzieli ax mod N , ponieważ tę drugą wielkość można przedstawić jako
ax +� kN . Zatem jeśli gcd(a, N) >�1, to ax ą�1 (mod N), niezależnie jaki będzie x. Stąd wynuka,
że a nie może mieć odwrotność modulo N.
W zasadzie jest to jedyny przypadek, w którym a nie jest odwracalne. Gdy gcd(a, N) =�1
(mówimy, że a i N są względnie pierwsze), rozszerzony algorytm Euklidesa daje nam liczby cał-
klwite x i y takie, że ax +� Ny =�1, co oznacz, że ax ��1 (mod N) . Zatem x jest szukaną odwrotno-
ścią a.
Przykład. Licząc gcd(28, 13), otrzymujemy dwie pierwszych kolomny tablicy
a b d x y
��a / b��
28 13 2 1 -6 13
13 2 6 1 1 -6
2 1 2 1 0 1
1 0 - 1 1 0
Otrzymujemy: -� 6�� 28 +�13��13 =�1, zatem 13��13 ��1 mod 28 i stąd 13 jest odwrotnością 13 modu-
lo 28.
Twierdzenie o dzieleniu modularnym. Dla dowolnego (a mod N) liczba a ma odwrotność
modulo N wtedy i tylko wtedy, gdy jest względnie pierwsze z N. Gdy odwrotność taka istnieje,
można ją obliczyć w czasie O(n3) (gdzie jak zwykle n oznacza liczbę bitów N), używając roz-
szerzonego algorytmu Euklidesa.
To rozwiązuje problem dzielenia modularnego: wykonując działania modulo N, możemy
dzielić przez liczby względnie pierwsze z N, i tylko przez takie. A dzielenie sprowadza się do
mnożenia przez odwrotność.
1.4. Testy pierwszości
Czy jest jakiś papierek lakmusowy, przy użyciu którego dowiemy się, czy dana liczba jest
pierwsza, nie podejmując próby rozłożenia jej na czynniki? Odpowiedzi poszukamy w pewnym
twierdzeniu z 1640 roku.
Małe twierdzenie Fermata. Jeśli p jest liczbą pierwszą, to dla każdego 1Ł� a <� p ,
p-�1
a ��1 (mod p) .
10
Dowód. Niech S oznacza zbiór liczb całkowitych modulo p różnych od zera, to znaczy
S =�{1,2,..., p -�1}. Oto kluczowa obserwacja: mnożąc te liczby przez a (modulo p), po prostu je
przestawiamy. Na przykład, dla a =� 5 , p =�11, otrzymujemy:
1��5 �� 5 (mod 11) , 2��5 ��10 (mod 11) , 3��5 �� 4 (mod 11) , 4��5 �� 9 (mod 11) , 5��5 �� 3 (mod 11) ,
6��5 �� 8 (mod 11), 7��5 �� 2 (mod 11), 8��5 �� 7 (mod 11) , 9��5 ��1 (mod 11) , 10��5 �� 6 (mod 11) .
Przeanalizujmy ten przykład nieco doklładniej. Z obliczeń wynika, że
{1,2,3,4,5,6,7,8,9,10}��{5��9 (mod11), 5��7 (mod11),..., 5�� 2 (mod11)}.
Wymnażając wszystkie liczby w obu zbiorach, dostajemy 10!�� 510 ��10! (mod11) , a dzieląc przez
10!, dostajemy 510 ��1 (mod11) , czyli to, co dokładnie chcieliśmy w przypadku a =� 5 , p =�11.
Uogólnijmy teraz rozumowanie na inne wartości a i p dla S =�{1,2,..., p -�1}. Udowodni-
my, że gdy elementy S są mnożone przez a modulo p, wszystkie powstałe liczby są równe i nie-
zerowe. A ponieważ są z zakresu [1, p -�1], muszą być permutacją zbioru S.
Liczby a ��i mod p są różne, ponieważ jeśli a ��i �� a �� j (mod p), to dzieląc obie strony
przez a, dostaniemy i �� j (mod p). Są różne od zera, ponieważ analogicznie z a ��i �� 0 (mod p)
wynika i �� 0 (mod p) . (Możemy dzielić przez a, ponieważ z założenia jest ono różne od zera, a
zatem względnie pierwsze z p).
Możemy teraz zapisać S na dwa sposoby:
S =�{1,2,..., p -�1} =�{a ��1 mod p, a �� 2 mod p,..., a ��( p -�1) mod p}.
Mnożąc jego elementy w każdej representacji, otrzymujemy
p-�1
( p -�1)!�� a ��( p -�1)! (mod p) .
Dzieląc przez ( p -�1)! (możemy to zrobić, ponieważ jest względnie pierwsze z p, gdyż p jest
pierwsza z zalożenia), otrzymujemy tezę twierdzenia.
Twierdzenie to prowadzi do  bezrozkładowego testu rozstrzygającego, czy liczba N jest
pierwsza:
a) Wybierz a i sprawdz
test Fermata: czy aN -�1 ��1 (mod N) ?
b) Odpowiedz
 Tak oznacza, że liczba N jest pierwsza,  Nie  że nie jest pierwsza.
Problem polega na tym, że twierdzenie Fermata nie jest warunkiem koniecznym i wystar-
czającym. Nie mówi ono, co się stanie, jeśli N nie jest pierwsze, więc w tym przypadku powyż-
szy schemat budzi wątpliwości. W zasadziejest możliwe, że liczba zlożona N przejdzie test
Fiermata (to znaczy aN -�1 ��1 (mod N) ) dla pewnych a. Na przykład, 341=�11��31 nie jest liczbą
pierwszą, a przecież 2340 ��1 (mod 341) . Niemniej moglibyśmy mieć nadzieję, że większość
wartości a spowoduje, iż liczba zlożona N nie przejdzie testu. W pewnum sensie, który wkrótce
doprzecyzujemy, jest to faktycznie prawda oraz uzasadnienie dla następnego algorytmu: zamiast
z góry ustalać jakaś wartość a, powinniśmy wylosować ją ze zbioru {1,2,..., N -�1}.
funkcja primality(N)
// wejście: dodatnia liczba całkowita N
// wyjście: tak/nie
Wylosuj dodatnią liczbę całkowitą a <� N
if aN -�1 ��1 (mod N) then
return Tak
else return Nie fi
11
Analizując zachowanie tego algorytmu, musimy najpierw uporać się z pewnym rzadko
występującym przypadkiem. Okazuje się, że pewne niezwykle rzadkie liczby złożone N, zwane
liczbami Carmichaela, przechodzą test Fermata dla wszystkich a względnie pierwszych z N. Dla
takich liczb nasz algorytm będzie działał z
le. Są to jednak patologicznie rzadkie przypadki i zo-
baczymy póz
niej, jak sobie z nimi radzić, więc na razie pominiemy te liczby.
Najmniejsza liczbą Carmichaela jest 561. Nie jest to liczba pierwsza: 561=� 3��11��17 , a
mimo to test Fermata zawodzi, ponieważ a560 ��1 (mod 561) dla wsystkich wartości a względnie
pierwszych z 561. Dziś wiemy, że liczb tego typu jest nieskończenie wiele, ale występują nie-
zwykle rzadko, na przykład wśród liczb mniejszych od 108 jest ich zaledwie 255.
W świecie wolnym od liczb Carmichaela nasz algorytm działa dobrze. Dowolna liczba
pierwsza oczywiście przejdzie test Fermata, który da prawidłową odpowiedz
. Jednakże dowolna
liczba złożona N niebędąca liczbą Carmichaela nie przejdzie testu Fermata dla pewnej wartości
a. Pokażemy teraz, że stąd natychmiast wynika, że N nie przejdzie testu dla co najmniej połowy
możliwych wartości a.
Lemat. Jeżeli aN -�1 ą�1 (mod N) dla pewnego a względnie pierwszego z N, to zachodzi to dla co
najmniej połowy liczb a <� N .
Dowód. Ustalmy pewna wartość a, dla której aN -�1 ą�1 (mod N) . Kluczowa jest obserwacja, że
każdy element b <� N , który powoduje, że liczba N przechodzi test Fermata (to znaczy
bN -�1 ��1 (mod N) ), ma bliz
niaka, a ��b , dla którego ten test wypada negatywnie:
(a ��b)N -�1 �� aN -�1 ��bN -�1 �� aN -�1 ą�1 (mod N) .
Co więcej, wszystkie elementy a ��b dla ustalonego a i różnych b są różne z tego samego powo-
du, dla którego a ��i ą� a �� j (mod p) w dowodzie testu Fermata: trzeba po prostu podzelić przez
a.
Z wzajemnej jednoznaczności funkcji b a� a ��b wynika, że test wypada negatywnie dla
przynajmniej tylu elementów, dla ilu wypada pozytywnie.
Pomijamy liczby Carmichaela, możemy zatem napisać:
Jeżeli N jest liczbą pierwszą, to aN -�1 ��1 (mod N) dla wszystkich a <� N .
Jeżeli N nie jest liczbą pierwszą, to aN -�1 ��1 (mod N) dla co najmniej połowy wartości
a <� N .
Prawdopodobieństwo określonego zachowania się algorytmu primality jest zatem
następujące:
P(algorytm primality zwraca  tak , gdy N jest liczbą pierwszą) = 1
P(algorytm primality zwraca  tak , gdy N nie jest liczbą pierwszą) Ł� �.
Możemy zmniejszyć ten bląd jednostronny, powtarzając całą procedurę wiele razy, losu-
jąc kilka wartości a i sprawdzając je wszystkie.
funkcja primality2(N)
// wejście: dodatnia liczba całkowita N
// wyjście: tak/nie
Wylosuj dodatnie liczby całkowite a1,a1,...,ak <� N
if aiN -�1 ��1 (mod N) dla wszystkich i =�1,2,...,k
then return Tak
else return Nie fi
To prawdopodobieństwo błędu maleje wykładniczo (jest mniej niż 1/ 2k ) i może być
zmniejszone dowolnie poprzez wybranie odpowiednio dużego k.
12
1.4.1. Generowanie losowych liczb pierwszych
Twierdzenie Lagrange a o liczbach pierwszych. Niech p� (x) będzie liczbą liczb pierwszych
Ł� x . Wtedy p� (x) � x / ln x lub dokładniej
p� (x)
lim =�1.
x��Ą�
(x / ln x)
Taka obfitość powoduje, że generowanie losowych n-bitowych liczb pierwszych jest pro-
ste:
a) Losujemy n-bitową liczbę N;
b) Uruchamiamy test pierwszości na N;
c) Jeśli liczba N pierwsza jest, wynikiem jest N, w przeciwnum razie powtarzamy proces.
Jak szybki jest ten algorytm? Jeśli wylosowana liczba N jest liczbą pierwszą, co zdarza się z
prawdopodobieństwem przynajmniej 1/ n , to na pewno przejdzie test. Tak więc w każdej iteracji
szansa, że procedura ta się zatrzyma, wynosi 1/ n . Zatem średnio zatrzyma się po O(n) itera-
cjach. W celu znalezenia jeszcze jednej liczby pierwszej tej samej długości będziemy zatem mu-
sieli przebadać około n losowo wybranych liczb w pobliżu N. Na przykład znalezienie 100-
cyfrowej liczby pierwszej wymagalłoby sprawdzenie około log10100 � 230 losowo wybranych
liczb 100-cyfrowych.
1.5. Kryptografia
Typowy scenariusz dla kryptografii można opisać z pomocą trójki bohaterów: Alicji i Boba,
chcących prywatności w komunikacji, oraz podsłuchującej Ewy, która chce dowiedzieć się, o
czym rozmawiają. Dla ustalenia uwagi, powiedzmy, że Alicja chce wysłać wiadomość x, zapisa-
ną binarne, do swojego przyjaciela Boba. Koduje ją jako e(x) , wysyła, a wówczas Bob, stosując
swoją funkcję deszyfrującą d(.) dekoduje ją: d(e(x)) =� x . Tutaj e(.) i d(.) są odpowiednimi prze-
kształceniami wiadomości. Dla bezpieczeństwa komunikacji funkcja szyfrująca e(.) musi być
wybrana w taki sposób, że bez znajomości d(.) Ewa nie potrafi nic zrobić z przechwyconą in-
formacją e(x).
Przez wieki kryptografia opierała się na czymś, co dziś nazywamy protokolami z kluczem
prywatnym. W takim schemacie Alicja i Bob spotykali się wcześniej i wspólnie wybierali tajny
kod, którym szyfrowali całą póz
niejszą korespondencję między sobą. Wczas jedyną nadzieją
Ewy było zebranie zakodowanych wiadomości i użycie ich w celu odtworzenia przynajmniej
części kodu.
Protokoly z kluczem publicznym, takie jak RSA (Rivesta-Shamira-Adlemana), umożli-
wiają Alicji wysłanie wiadomości do Boba bez wcześniejszego spotkania. Funkcja szyfrująca
Boba e(.) jest dostępna dla wszystkich i Alicja może zaszyfrować swoją wiadomość za pomocą
tej funkcji, tym samym zamykając ją na cyfrowy klucz. Jedynie Bob zna klucz pozwalający
szybko otworzyć ten cyfrowy zamek: jest nim funkcja deszyfrująca d(.). Istotne jest to, że Alicja
i Bob muszą wykonać jedynie proste obliczenia, aby zamykać i otwierać wiadomość  operacje,
z którymi mógłby poradzić sobie każdy kalkulator. Dla kontrastu, aby otworzyć wiadomość bez
pomocy klucza, Ewa musi wykonać takie operacje, jak rozkład na czynniki pierwsze wielkich
liczb, które wymagają mocy obliczeniowej większej miż moc osiągnięta przez sprzężenie naj-
mocniejszych komputerów świata. Ta fascynująca gwarancja pozwala na bezpieczne przeprowa-
dzanie w sieci takich operacji, jak wysylanie numerów kart kredytowych do firm przez internet.
1.5.1. Szyfr z kluczem jednorazowym
Dla bezpeczności przesylania wiadomości można zastosować pewną funkcją szyfrującą:
e: ��wiadomośćń� �� ��zakodowana wiadomośćń�
Oczywiście funkcja e(.) musi być odwracalna, aby możliwe było deszyfrowanie, a zatem jest bi-
jekcją. Jej odwrotnością jest funkcja deszyfrująca d(.).
13
 W prokokole szyfrowania z kluczem jednorazowym Alicja spotka się wcześniej z Bobeem
i w tajemnicy wybierają ciąg binarny r o tej samej długości (powiedzmy n bitów), co wiadomość
x, którą Alicja prześle póz
niej. Funkcją szyfrującą Alicji jest wówczas bitowa różnica syme-
tryczna (ang. exclusive-or, w skrócie XOR), er (x) =� x �� r : każdy bit zakodowanej wiadomości
jest różnicą symetryczną odpowiadających bitów w x i r. Na przykład, jeśli r =� 01110010 , to
wiadomość 11110000 jest szyfrowana w ten sposób:
er (11110000) =�11110000 �� 01110010 =�10000010 .
Funkcja er jest bijekcją prowadzącą z ciągów n-bitowych w ciągi n-botowe, co widać dziękite-
mu, ż jest swoją odwrotnością:
er (er (x)) =� (x �� r) �� r =� x �� (r �� r) =� x �� 0 =� x ,
gdzie 0 jest ciągiem złożonym z samycg zer. Tak więc Bob może odszyfrować wiadomość od
Alicji, stosując tę samą funkcję szyfrującą po raz drugi: dr (y) =� y �� r .
W jaki sposób Alicja i Bob powinni wybrać r, aby schemat tenbył bezpieczny? Po prostu:
powinni wylosować r, dla każdego bitu rzucając monetą, aby powstały ciąg był z jednakowym
prawdopodobieństwem dowolnym elementem z {0,1}n .
Słabą stroną szyfru z kluczem jednorazowym jest to, że nie powinniśmy go używać po-
nownie, stąd jego nazwa. Kolejna wiadomość zakodowana tym samym kluczem nie byłaby bez-
pieczna, bo gdyby Ewa znała x �� r i z �� r dla dwóch wiadomości x i z, to modłaby obliczyć
różnicę symetryczną i otrzymać x �� z , co mogłoby być istotną informacją. Na przykład, pozwa-
la sprawdzić, czy te dwie wiadomości zaczynają się lub kończą tak samo, oraz jeśli jedna wia-
domość zawiera długi ciąg zer (co jest bardzo prawdopodobne, gdy wiadomość jest obrazkiem),
to odpowiednia część drugiej wiadomości wyjdzie na jaw. Zatem losowy ciąg, który Alicja i Bob
ustalają, powinien mieć długość równa sumie długości wszystkich wiadomości, które chcą mię-
dzy sobą przesylać.
1.5.2. Protokoł RSA
Protokoł RSA jest prykładem kryptograficznego protokołu z kluczem publicznym: każdy może
wyslać wiadomość do kogokolwiek, używając publicznie dostępnych informacji. Każdy posiada
klucz publiczny znany całemu światu oraz klucz prywatny znany tylko jej lub jemu. Gdy Alicja
chce wysłać do Boba wiadomość x, szyfruje ją za pomocą jego klucza publicznego. Bob do od-
szyfrowania używa swojego klucza prywatnego i otrzymuje x. Ewa może zobaczyć tyle zaszy-
frowanych wiadomości przeznaczonych dla Boba, ile tylko chce, ale nie będzie w stanie ich od-
szyfrować, jeśli spełnimy pewne proste wymagania.
System RSA jest oparty w znacznym stopniu na teorii liczb. Wyobraz
my sobie wiadomo-
ści od Alicji do Boba jako liczby modulo N. Wiadomości większe niż N są dzielone na mniejsze
kawałki. Funkcja szyfrująca będzie wówczas bijekcją na {0,1,..., N -�1}, a funkcja deszyfrująca
będzie do niej odwrotna.
Własność. Niech p i q będą liczbami pierwszymi i niech N =� p ��q . Dla dowolnego e względnie
pierwszego z ( p -�1)(q -�1) :
1. Odwzorowanie x a� xe mod N jest bijecja na {0,1,..., N -�1}.
2. Ponadto, odwzorowanie odwrotne łatwo skonstruować: niech d będzie odwrotnością
e modulo ( p -�1)(q -�1) . Wówczas dla każdego x��{0,1,..., N -�1},
d
(�xe)� �� x mod N .
Pierwsza własność mówi, że odwzorowanie x a� xe mod N jest rozsądnym sposobem
kodowania wiadomości x; nie tracimy żadnej informacji. Zatem, jeśli Bob opublikuje (N,e) jako
swój klucz publiczny, każdy będzie mógł go użyć w celu wysłania zaszyfrowanych wiadomości
14
do Boba. Druga własność mówi zaś, w jaki sposób deszyfrować. Bob powinien zatrzymać war-
tość d jako swój klucz prywatny, którym może odszyfrować wszystkie wiadomości przychodzące
do niego poprzez podniesienie ich do potęgi d modulo N.
Przykład. Niech N =� 55 =� 5��11. Wybieramy jako wykładnik szyfrujący e =� 3, zatem
spełniony jest warunek gcd(e,( p -�1)(q -�1)) =� gcd(3,40) =�1. Wykładnik deszyfrujący wynosi
wtedy d =� 3-�1 mod 40 =� 27. Teraz dla każdej wiadomości x mod55 , zaszyfrowany x wynosi
y =� x3 mod55, natomiast odszyfrowany y jest x =� y27 mod55. Zatem, na przykład, jeśli x =�13,
to y =�133 =� 52mod55 , a 13 =� 5227 mod55.
Udowodnijmy powyższe stwierdzenie, a potem zbadajmy bezpeczeństwo systemu RSA.
Dowód. Jeśli odwzorowanie x a� xe mod N jest odwracalne, to musi być bijekcją. Stąd punkt 2
implikuje punkt 1. Aby udowodnić punkt 2, najpierw zauważmy, że e jest odwracalne modulo
d
( p -�1)(q -�1) , gdyż jest względnie pierwsze z tą liczbą. Aby zobaczyć, że (�xe)� �� x(mod N) ,
zbadamy wykładnik. Ponieważ ed ��1mod( p -�1)(q -�1) , możemy napisać ed w postaci
1+� k( p -�1)(q -�1) dla pewnego k. Musimy teraz udowodnić, że różnica
xed -� x =� x1+�k( p-�1)(q-�1) -� x
wynosi zawsze 0 modulo N. Druga postać wyrażenia jest wygodna, gdyż można uprościć, stosu-
p-�1
jąc małe twierdzenie Fermata. Jest ono podzielne przez p (bo x ��1mod p ) i podobnie przez q.
Ponieważ p i q są liczbami pierwszymi, wyrażenie to musi być również podzielne przez ich ilo-
czyn N. Stąd xed -� x =� x1+�k( p-�1)(q-�1) -� x �� 0(mod N) , dokladnie to, co chcieliśmy.
Jak to działa?
Bob wybiera klucz publiczny i prywatny.
1. Najpierw losuje dwie duże (n-bitowe) liczby pierwsze p i q.
2. Jego kluczem publicznym jest (N,e) , gdzie N =� pq , a e jest 2n-bitową liczbą
względnie pierwsza z ( p -�1)(q -�1) . Często wybierane jest e =� 3, ponieważ umożli-
wia szybkie szyfrowanie.
3. Jego kluczem prywatnym jest d, odwrotność e modulo ( p -�1)(q -�1) , obliczona roz-
szerzonym algorytmem Euklidesa.
Alicja chce wyslać wiadomość do Boba.
1. Szuka jego klucza publicznego (N,e) i wysyła mu y =� xe mod N , obliczone za po-
mocą efektywnego algorytmu potęgowania modularnego.
2. Bob dekoduje wiadomość, obliczając yd mod N .
Bezpieczeństwo RSA opiera się na prostym założeniu:
Znając N, e oraz y =� xe mod N , nie da się szybko obliczyć x.
Dla odszyfrowania wiadomości trzeba razłożyć N na czynniki pierwsze, aby uzyskać p i q, i
wówczas obliczyć d, odwracając e modulo ( p -�1)(q -�1) , ale ten rozkład jest bardzo trudny.
15