W2 Kodowanie i Kryptografia Algebra 1 2g, PWr, IV Semestr, Kryptografia i Kodowanie
[ Pobierz całość w formacie PDF ]
Kryptografia Algebra dr Robert Borowiec pokój 908, C-5 tel. 3203083 e-mail: robert.borowiec@ita.pwr.wroc.pl www: lstwww.ita.pwr.wroc.pl/ ~ RB/ Wykład II 2-godziny Arytmetyka modularna Kongruencja jest to przystawanie liczb a i b według modułu m (modulo m ) i jest zapisywana w postaci: a ≡ b (mod m ) lub a ≡ m b, gdy m|(a-b) Liczba a przystaje do b wtedy, gdy m dzieli bez reszty a-b © Robert Borowiec Kryptografia, Wykład II Algebra, strona 2/25 Elementy algebry ¾ Pojęcia podstawowe grupa, pierścień, ciało arytmetyka modularna funkcja Eulera ¾ Przestrzenie wektorowe wielomiany pierwotne wielomiany minimalne © Robert Borowiec Kryptografia, Wykład II Algebra, strona 3/25 Grupa Grupa Q jest zbiorem elementów, w którym jest określone pewne jednowartościowe dwuargumentowe działanie, umownie zwane dodawaniem "+", oraz są spełnione cztery aksjomaty dla dowolnych a , b , c ∈ Q : © Robert Borowiec Kryptografia, Wykład II Algebra, strona 4/25 Grupa-aksjomaty 1) suma dowolnych elementów jest elementem grupy (zamkniętość): a + b ∈ Q; (1a) 2) wynik sumowania nie zależy od kolejności składników sumy (łączność): a + (b + c) = (a + b) + c; (1b) 3) istnieje element neutralny e (prawo identyczności): a + e = e + a = a, e ∈ Q ; (1c) 4) istnieją elementy odwrotne (prawo odwrotności): a + a = e a ∈ Q . (1d) © Robert Borowiec Kryptografia, Wykład II Algebra, strona 5/25 Grupa cd.. Przykład 1: Zbiór wszystkich liczb rzeczywistych (łącznie z zerem) stanowi grupę względem operacji zwyczajnego dodawania. Przykład 2: Zbiór wszystkich liczb rzeczywistych z wyłączeniem zera stanowi grupę względem operacji zwyczajnego mnożenia . Grupa jest grupą przemienną lub abelową , jeśli zachodzi równość a + b = b + a. (2) Przykład grupy nieprzemiennej: zbiór macierzy stopnia n, których wyrazami są dowolne liczby rzeczywiste, jest grupą nieprzemienną względem operacji mnożenia macierzowego. © Robert Borowiec Kryptografia, Wykład II Algebra, strona 6/25 Pierścień Pierścień R jest zbiorem elementów, dla których są zdefiniowane dwa działania: a + b - zwane umownie dodawaniem oraz a·b - zwane umownie mnożeniem, przy czym a , b są elementami R. Zbiór R jest pierścieniem, jeśli są spełnione następujące aksjomaty: © Robert Borowiec Kryptografia, Wykład II Algebra, strona 7/25 Pierścień-aksjomaty 1) zbiór R jest grupą abelową ze względu na dodawanie a + b = b + a; (3a) 2) zbiór R jest zamknięty ze względu na operację mnożenia a·b ∈ R; (3b) 3) mnożenie jest łączne, to znaczy dla dowolnych a , b , c ∈ R zachodzi a · ( b · c ) = ( a · b ) ·c ; (3c) 4) obowiązuje prawo rozdzielności dodawania względem mnożenia, to znaczy a· ( b + c ) = a · b + a · c . (3d) © Robert Borowiec Kryptografia, Wykład II Algebra, strona 8/25 Pierścień-przykład Zbiór liczb stanowiących klasy reszt modulo dowolna liczba całkowita m jest pierścieniem względem operacji dodawania modulo m i operacji mnożenia modulo m . Dla m = 4 reguły dodawania i mnożenia są następujące: + 0 1 2 3 • 0 1 2 3 0 0 1 2 3 0 0 0 0 0 1 1 2 3 0 1 0 1 2 3 2 2 3 0 1 2 0 2 0 2 3 3 0 1 2 3 0 3 2 1 © Robert Borowiec Kryptografia, Wykład II Algebra, strona 9/25 Ciało Ciało C jest to pierścień przemienny, w którym istnieje element neutralny względem mnożenia , spełniający prawo identyczności ε ∈ C , a ⋅ ε = ε ⋅ a = a , (4a) a każdy niezerowy element ma swój element odwrotny względem mnożenia a − 1 ∈ C , a ⋅ a − 1 = a − 1 ⋅ a = ε . (4b) Przykładem ciała jest zbiór wszystkich liczb rzeczywistych. © Robert Borowiec Kryptografia, Wykład II Algebra, strona 10/25 [ Pobierz całość w formacie PDF ] |