Akade mia 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

Laboratorium 1

Wybrane zagadnienia teorii liczb

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 ws zystkich liczb pierws zych mniejs zych 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ądź 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 znaleźć 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 przejdź do 1.

Jednak do wyznaczenia odwrotności modularnej mod n można wykorzystać też rozs zerzony
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 imple mentacji algorytmów w C++

1. Znajdowanie liczb pierws zych z zadanego prze działu

prime_numbers.cpp (korzystając z algorytmu Sito Eratostenesa) [3]

2. Sprawdzanie czy liczby są względnie pie rwsze

eea.cpp (korzystając z rozszerzonego Algorytmu Euclidesa) na podstawie [1]

III.

Lite ratura:
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