W2_Kodowanie i Kryptografia_Algebra 1_2g.pdf

(481 KB) Pobierz
Microsoft PowerPoint - W2_Kodowanie i Kryptografia_Algebra 1_2g.ppt
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
317372535.033.png 317372535.034.png 317372535.035.png 317372535.036.png 317372535.001.png 317372535.002.png 317372535.003.png
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
317372535.004.png 317372535.005.png 317372535.006.png 317372535.007.png 317372535.008.png 317372535.009.png 317372535.010.png
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
317372535.011.png 317372535.012.png 317372535.013.png 317372535.014.png 317372535.015.png 317372535.016.png 317372535.017.png 317372535.018.png
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
317372535.019.png 317372535.020.png 317372535.021.png 317372535.022.png 317372535.023.png 317372535.024.png 317372535.025.png
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
317372535.026.png 317372535.027.png 317372535.028.png 317372535.029.png 317372535.030.png 317372535.031.png 317372535.032.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin