W2 Kodowanie i Kryptografia ...

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

(
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 ]
  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • diabelki.xlx.pl
  • Podobne
    Powered by wordpress | Theme: simpletex | © Spojrzeliśmy na siebie szukając słów, które nie istniały.