Kryptografia-wyklad_07.pdf

(39 KB) Pobierz
Kryptografia-slajdy.dvi
Wykład 7
Kongruencje
7.1 Relacja przystawania modulo m
Definicja 7.1. Niech m 2 N. Wprowadźmy w zbiorze liczb całkowitych relację kongru
encji (przystawania) liczb modulo m, oznaczaną symbolem „ (mod m)”, następują
co:
8 a, b∈Z
a b (mod m) () (a MOD m) = (b MOD m).
Twierdzenie 7.1. Relacja przystawania modulo m jest relacją równoważności. Klasy
abstrakcji tej relacji są reprezentowane jednoznacznie przez elementy zbioru Z m .
Twierdzenie 7.2. Niech m, n będą dowolnymi liczbami naturalnymi oraz a, b, c, d —
dowolnymi liczbami całkowitymi. Wówczas
(a) Jeżeli a b (mod m) i c d (mod m), to a + c b + d (mod m) i ac bd
(mod m).
(b) Jeżeli a b (mod m) oraz d|m i d 2 N, to a b (mod d).
(c) Jeżeli a b (mod m), a b (mod n) i NWD(m, n) = 1, to a b (mod mn).
7.2 Kongruencje liniowe
Zadanie: Dla danych liczb całkowitych a, b oraz liczby naturalnej m znaleźć wszystkie
liczby całkowite x, dla których zachodzi
ax b (mod m).
(7.1)
Zadanie takie będziemy nazywać liniowym równaniem kongruencyjnym lub, krótko, kon
gruencją liniową.
22
Uwaga 7.1. Dla dowolnych liczb a, b 2
Z
oznaczmy a 0
= a MOD m i b 0
= b MOD m.
Wówczas kongruencja
ax b (mod m)
ma taki sam zbiór rozwiązań, jak kongruencja
a 0 x b 0
(mod m).
(7.2)
Uwaga 7.2. Jeżeli a 0 = 0 (czyli: a 0 (mod m)), to kongruencja (7.2) ma rozwiązanie
wtedy i tylko wtedy, gdy również b 0 = 0 i wówczas rozwiązaniem jest każda liczba
całkowita.
Uwaga 7.3. Jeżeli m = 1, to rozwiązaniem kongruencji (7.2) jest każda liczba całkowita.
Uwaga 7.4. Poszukiwanie rozwiązania kongruencji (7.2) w zbiorze Z m jest równoważne
szukaniu rozwiązań równania a 0 · m x = b 0 w pierścieniu Z m .
Twierdzenie 7.3. Niech m 2 N i a 2 Z m , b 2 Z m będą dowolnymi liczbami. Wówczas:
1 0 . Jeżeli NWD(a, m) = 1, to istnieje dokładnie jedno rozwiązanie x 0
2 Z m kongruencji
(7.1). Każde inne rozwiązanie x tej kongruencji ma postać
x = x 0 + km
dla pewnego k 2 Z.
2 0 . Jeżeli NWD(a, m) = d > 1, to rozwiązanie kongruencji (7.1) istnieje wtedy i tylko
wtedy, gdy d|b. Jeżeli d|b, to kongruencja (7.1) jest równoważna kongruencji
a ′ x b ′
(mod m ′ ),
(7.3)
gdzie a ′ = a/d, b ′ = b/d oraz m ′ = m/d.
7.3 Układy kongruencji
Twierdzenie 7.4 (Chińskie twierdzenie o resztach). Niech m 1 , m 2 , . . . , m k 2 N
będą liczbami parami względnie pierwszymi i m = m 1 m 2 ·. . .·m k . Wówczas dla dowolnych
liczb całkowitych a 1 , a 2 , . . . , a k układ kongruencji
8
<
x a 1
(mod m 1 ),
x a 2
(mod m 2 ),
(7.4)
:
· · ·
· · ·
x a k
(mod m k )
ma dokładnie jedno rozwiązanie x 0
2
Z m . Każde inne rozwiązanie x układu (7.4) ma
postać x = x 0 + lm dla pewnego l 2 Z.
23

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin