Kryptografia-wyklad_05.pdf

(33 KB) Pobierz
Kryptografia-slajdy.dvi
Wykład 5
Struktury algebraiczne
5.1 Działania modularne
Dla dowolnej liczby naturalnej m > 1 oznaczmy
Z m
= {0, 1, . . . , m − 1},
Z m
= {1, . . . , m − 1},
Z m
= {n 2 Z m
: n?m}.
Zauważmy, że
Z m
Z m
Z m .
W zbiorze Z m
wprowadzamy działania wewnętrzne dodawania modulo m + m
i mno
żenia modulo m · m
następująco: dla dowolnych a, b 2 Z m
przyjmujemy
a + m b = (a + b) MOD m oraz a · m b = (a · b) MOD m.
Wewnętrzność tak wprowadzonych działań jest oczywista.
Lemat 5.1. Niech m 2 N \ {1} i a, b 2 Z. Wtedy
(a) (a + b) MOD m = [(a MOD m) + (b MOD m)] MOD m,
(b) (a · b) MOD m = [(a MOD m) · (b MOD m)] MOD m.
Korzystając z definicji działań modulo m możemy zapisać równości występujące w
lemacie w poniższej postaci:
(a) (a + b) MOD m = (a MOD m) + m (b MOD m),
(b) (a · b) MOD m = (a MOD m) · m (b MOD m).
Twierdzenie 5.1. Dla dowolnej liczby naturalnej m para (Z m , + m ) jest grupą abelową.
15
Zauważmy, że:
• Działanie + m
nie jest wewnętrzne w zbiorach Z m
i Z m
dla każdej liczby całkowitej
m > 2.
• Działanie · m
nie jest wewnętrzne w zbiorach Z m , jeżeli m jest liczbą złożoną.
• Działanie · m
jest wewnętrzne w zbiorze Z m
dla każdej liczby całkowitej m > 1.
5.2 Element odwrotny względem mnożenia modulo
m
Definicja 5.1. Niech m > 1 będzie liczbą naturalną i a 2 Z m . Jeżeli istnieje taka liczba
b 2 Z m , że a · m b = 1, to nazywamy ją elementem odwrotnym do a modulo m i oznaczamy
symbolem a −1
mod m.
Twierdzenie 5.2. Niech m > 1 będzie liczbą naturalną i a 2 Z. Wówczas a posiada
element odwrotny modulo m wtedy i tylko wtedy, gdy NWD(a, m) = 1.
Twierdzenie 5.3. Dla dowolnej liczby naturalnej m > 2 para (Z m , · m ) jest grupą abe
lową.
Wniosek 5.1. Niech m > 2 będzie liczbą naturalną. Para (Z m , · m ) jest grupą abelową
wtedy i tylko wtedy, gdy m jest liczbą pierwszą.
Wniosek 5.2. Jeżeli p 2 P, to (Z p , + p , · p ) jest ciałem przemiennym.
16

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin