Akademia Górniczo-Hutnicza im. Stanisława Staszica w
Krakowie
Wydział Elektrotechniki, Automatyki Informatyki i Inżynierii
Biomedycznej
Kryptografia i systemy utajania informacji
Inżynieria Biomedyczna, studia I stopnia, III rok
Wybrane zagadnienia teorii liczb
Laboratorium 1 2 x 45min
I. Podstawy teoretyczne
Liczbę naturalną n nazywamy liczbą pierwszą, jeżeli dzieli się tylko przez 1 i przez samą
siebie. Jeżeli n ma jeszcze inne dzielniki to nazywamy ją liczbą złożoną.
1. Znajdowanie wszystkich liczb pierwszych mniejszych od n
Algorytm: Sito Eratostenesa
1) Ze zbioru liczb naturalnych z przedziału [2, n], tj. {2, 3, 4,& , n}, wybieramy
najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej
samej, to jest 4, 6,8,& .
2) Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy
wszystkie jej wielokrotności większe od niej samej: 6, 9, 13,& przy czym nie
przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej
niż raz.
3) Według tej samej procedury postępujemy dla liczby 5, a następnie dla 7, 11, 13; aż do
sprawdzenia wszystkich niewykreślonych wcześniej liczb.
4) Wykreślanie powtarzamy do momentu, gdy liczba i, której wielokrotność wykreślamy,
bÄ™dzie wiÄ™ksza niż "n.
5) Dla danej liczby n wszystkie niewykreślone liczby mniejsze, bądz
równe n są liczbami
pierwszymi.
2. Arytmetyka modularna (arytmetyka reszt)
Niech . Wtedy wynikiem operacji dzielenia modulo a przez m, oznaczamy
jest reszta Liczba całkowita m jest nazywana modułem dzielenia
(redukcji) , zakładamy, że m>1. Zatem dzielenie modulo m zwraca jako resztę liczbę r
należącą do zbioru {0, ...,m - 1}.
Przykłady: , dla liczb parzystych , a dla
nieparzystych
Operacje dzielenia modulo mogą być też stosowane do sum i iloczynów liczb całkowitych,
dla zachodzą następujące zależności:
·ð (a Ä… b) mod m [(a mod m) Ä… (b mod m)] mod m
·ð (a * b) mod m [(a mod m) * (b mod m)] mod m
Własności dzielenia modulo m:
, m > 1 moduł
(a) a 0 mod m wtedy i tylko wtedy gdy m | a
(b) a a mod m
(c) a b mod m wtedy i tylko wtedy gdy b a mod m
(d) jeżeli a b mod m i b c mod m wtedy a c mod m
(e) jeżeli a b mod m i c d mod m wtedy
a + c b + d mod, m a - c b - d mod m, ac bd mod m
Mówimy, że liczby całkowite a i b są kongruentne według modułu m, co zapisujemy
( liczba całkowita) wtedy i tylko wtedy gdy takie, że
(m jest podzielnikiem różnicy a-b).
Zatem a jest kongruentne z b modulo m wtedy i tylko wtedy gdy a = km + b, gdzie k jest
całkowite. W związku z tym możemy podzielić a przez m i otrzymać resztę b należącą do
zbioru {0, ...,m - 1}.
Przykłady:
m = 2
liczby całkowite kongruentne z 2 : ... - 6,-4 - 2, 0, 2, 4, 6, ...
liczby całkowite kongruentne z 1: ... - 7,-5,-3,-1, 1, 3, 5, 7, ...
m = 3
liczby całkowite kongruentne z 5: ... - 4,-1, 2, 5, 8, 11, ...
m = 7
liczby całkowite kongruentne z 6: ...,-8,-1, 6, 13, 20, ....
Działania modulo:
dodawanie:
x y = x + y mod m
mnożenie:
x y = x · y mod m
3. Obliczanie odwrotności liczby w arytmetyce modularnej
Dla danej liczby należy znalez
ć jedną liczbę x należącą do tego przedziału,
która spełnia warunek: ax mod n=1.
Przykład: liczby 3 i 7 są odwrotnościami w arytmetyce modulo 10, ponieważ 3*7 = 21 mod
10 = 1.
Twierdzenie:
Równanie ax mod n=1 ma jednoznaczne rozwiązanie, gdy liczby a i n są względnie pierwsze,
czyli NWD(a,n)=1.
Do wyznaczanie NWD dwóch liczb można wykorzystać algorytm Euklidesa. NWD liczb a i
b można obliczyć wykorzystującą operację reszty z dzielenia (modulo):
1. oblicz c jako resztÄ™ z dzielenia a przez b
2. zastÄ…p pozycjÄ™ a liczbÄ… b, a pozycjÄ™ b liczbÄ… c
3. jeżeli pozycja b = 0, to szukane NWD = a, w przeciwnym wypadku przejdz
do 1.
Jednak do wyznaczenia odwrotności modularnej mod n można wykorzystać też rozszerzony
Algorytm Euklidesa, który pozwala na wyznaczenie największego wspólnego podzielnika d
dwóch liczb a i b oraz takich liczb całkowitych x i y, które spełniają zależność ax+by = d.
Wystarczy, że w każdym kroku przechowywana będzie informacja o kolejnych ilorazach.
Przykład: Szukamy NWD liczb 186 i 24.
W algorytmie Euklidesa uzyskuje się wyniki pośrednie:
1) a=186, b=24, 186/24=7 i reszta c=18
2) a=24, b=18, b , więc 24/18= 1 i reszta c=6
3) a=18, b= 6, b , więc 18/6=3 i reszta c=0
4) a=6, b=0, więc NWD(180, 24)=6
Natomiast przepisując wszystkie równania w taki sposób, by w pierwszym równaniu po
prawej stronie występowała suma pewnych wielokrotności liczb 174 i 18, a w następnyc h
równaniach kombinacje liniowe 174, 18 lub liczb, które wystąpiły po lewej stronie we
wcześniejszych równaniach.
1) 18=1"186+(-7)"24
2) 6=1"24+(-1)"18
3) 0=1"18+(-3)"6
Kluczowa dla rozszerzonego algorytmu Euklidesa staje się możliwość stopniowego
zastępowania tych liczb przez kombinacje liniowe liczb wejściowych aż do otrzymania
równości: NWD(a,b)=kombinacja liniowa liczb a, b, np.
6=1"24+(-1)"18=1"24+(-1)"(1"186+(-7)"24)= (-1)"186+8"24
II. Omówienie przykładowych implementacji algorytmów w C++
1. Znajdowanie liczb pierwszych z zadanego przedziału
prime_numbers.cpp (korzystajÄ…c z algorytmu Sito Eratostenesa) [3]
2. Sprawdzanie czy liczby są względnie pierwsze
eea.cpp (korzystajÄ…c z rozszerzonego Algorytmu Euclidesa) na podstawie [1]
III. Literatura:
1. Ogiela MR, Podstawy kryptografii, Wydawnictwa AGH, 2000
2. Rutkowski J, Algebra abstrakcyjna w zadaniach, Wydawnictwa Naukowe
PWN, 2009
3. http://pl.wikipedia.org/wiki/Sito_Eratostenesa#C.2B.2B