Kryptografia-wyklad_04.pdf

Wykład 4

Podzielność i NWD

4.1 Podzielność i liczby pierwsze

Deﬁnicja 4.1. Niech a, b ∈ Z, a = 0. Mówimy, że liczba a dzieli liczbę b (lub: b jest

podzielna przez a albo a jest dzielnikiem b) i piszemy a|b, gdy istnieje taka liczba cał

kowita d, że b = ad. Dzielnikiem nietrywialnym liczby b nazywamy każdy jej dzielnik

dodatni różny od 1 i od b.

Deﬁnicja 4.2. Liczbę całkowitą nazywamy złożoną, jeżeli ma ona dzielnik nietrywialny.

Deﬁnicja 4.3. Liczbę naturalną nazywamy pierwszą, jeżeli ma ona dokładnie dwa róż

ne dzielniki dodatnie. Zbiór wszystkich liczb pierwszych oznaczamy symbolem P.

Twierdzenie 4.1. Zbiór P zawiera nieskończenie wiele elementów.

Twierdzenie 4.2 (o rozkładzie na czynniki pierwsze). Niech m będzie dowolną licz

bą naturalną. Istnieją wówczas i są określone jednoznacznie ciągi: p 1

< p 2

< . . . < p k

liczb pierwszych oraz a 1 , a 2 , . . . , a k liczb naturalnych takie, że

m = p a 1

p a 2

. . . p a k

4.2 Iloraz całkowity i reszta

Deﬁnicja 4.4. Podłogą lub dolną częścią całkowitą liczby x ∈ R nazywamy liczbę

⌊x⌋ = max{n ∈ Z : n x}.

Suﬁtem lub górną częścią całkowitą liczby x ∈ R nazywamy liczbę

⌈x⌉ = min{n ∈ Z : n x}.

Twierdzenie 4.3. Niech p ∈ N. Dla każdej liczby całkowitej n liczby

q =

oraz r =

−

są jedynymi liczbami takimi, że q ∈ Z i r ∈ {0, 1, . . . , p − 1} oraz zachodzi równość

n = p q + r .

(4.1)

Deﬁnicja 4.5. Niech p będzie dowolną liczbą naturalną. Dla każdej liczby n ∈ Z liczby

n DIV p =

i n MOD p =

−

p .

nazywamy odpowiednio ilorazem całkowitym liczby n przez p i resztą z dzielenia liczby

n przez p lub resztą modulo p.

Przy tak wprowadzonych oznaczeniach równość (4.1) można zapisać w postaci:

n = (n DIV p) p + (n MOD p) .

(4.2)

4.3 Największy wspólny dzielnik

Deﬁnicja 4.6. Niech a i b będą dwiema liczbami całkowitymi, z których przynajmniej

jedna jest różna od 0. Największym wspólnym dzielnikiem liczb a i b nazywamy najwięk

szą liczbę całkowitą d taką, że d|a i d|b. Liczbę tę oznaczamy symbolem NWD(a, b).

Uwaga 4.1. (a) Jeżeli a ∈ Z, to NWD(a, b) = NWD(a, 0) = |a|.

(b) Dla całkowitych liczb a, b = 0 mamy NWD(a, b) = NWD(|a|, |b|)

Deﬁnicja 4.7. Liczby a, b ∈ Z nazywamy względnie pierwszymi, gdy NWD(a, b) = 1.

Piszemy wtedy: a⊥b.

Twierdzenie 4.4. Jeżeli a, b ∈ N są takimi liczbami, że a > b, to

NWD(a, b) = NWD(b, a MOD b).

4.4 Algorytm Euklidesa

Dane: Liczby naturalne a, b.

Szukane: NWD(a, b).

Zmienne pomocnicze: r, q.

Start

r := a;

q := b;

dopóki q > 0 wykonuj

p := r MOD q

r := q

q := p;

zwróć r

Stop

Twierdzenie 4.5. Algorytm Euklidesa działa poprawnie, tzn. otrzymana w wyniku dzia

łania tego algorytmu liczba r = NWD(a, b).

Twierdzenie 4.6 (o liniowym rozkładzie NWD). Niech a, b będą dwiema liczbami

naturalnymi i d = NWD(a, b). Istnieją wówczas liczby s, t ∈ Z takie, że

sa + tb = d.

Wniosek 4.1. Liczby naturalne a i b są względnie pierwsze wtedy i tylko wtedy, gdy

istnieją liczby całkowite s i t takie, że

sa + tb = 1.

Wniosek 4.2. Jeżeli a, b są liczbami naturalnymi i c jest liczbą całkowitą, to równanie

ax + by = c

ma rozwiązanie (x, y) będące parą liczb całkowitych wtedy i tylko wtedy, gdy liczba c jest

całkowitą wielokrotnością NWD(a, b).

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: