W3_Kodowanie i Kryptografia_Algebra 2_2g.pdf

(524 KB) Pobierz
Microsoft PowerPoint - W3_Kodowanie i Kryptografia_Algebra 2_2g.ppt
Kodowanie i kryptografia
Algebra 2
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki
pokój 908, C-5
tel. 3203083
e-mail: robert.borowiec@ita.pwr.wroc.pl
www: lstwww.ita.pwr.wroc.pl/ ~ RB/
Wykład III
2-godziny
Wielomiany
Zdefiniujemy przekształcenie
() ∑ −
=
n
1
F a
≡
a
i x
i
i
0
które ciągowi a =( a n- 1 , a n- 2 ,..., a 1 , a 0 ) przyporządkowuje, w
sposób wzajemnie jednoznaczny, wielomian
a
()
=
a
x
n
−
1
+
a
x
n
−
2
+
⋅
⋅
⋅
+
a
x
1
+
a
x
0
n
−
n
−
2
1
0
Przykłady:
111 ⇔ x 2 +x+1; 101 ⇔ x 2 +1; 001 ⇔ 1; 100⇔ x 2
Robert Borowiec
*
Kodowanie i kryptografia
Wykład III, strona 2/30
x
1
446365600.032.png 446365600.033.png 446365600.034.png 446365600.035.png 446365600.001.png 446365600.002.png 446365600.003.png
Wielomiany cd..
¾ Dodawanie wielomianów sprowadza się do
dodawania ich współczynników w
odpowiednim ciele.
Spełniony jest aksjomat zamkniętości w
odniesieniu do operacji dodawania
Nie spełniony jest aksjomat zamkniętości w
odniesieniu do operacji zwykłego mnożenia
Robert Borowiec
Kodowanie i kryptografia
Wykład III, strona 3/30
Wielomiany cd..
¾ Zdefiniujmy wynik operacji mnożenia dwóch
wielomianów jako reszty z podziału iloczynu przez pewien
wielomian p(x) stopnia n
cx R axbx
() ( ) ( )
[ ]
Wielomian p(x) musi być wielomianem pierwszym, tzn.
wielomianem nie rozkładalnym w ciele CG(p)
Robert Borowiec
Kodowanie i kryptografia
Wykład III, strona 4/30
()=
px
446365600.004.png 446365600.005.png 446365600.006.png 446365600.007.png 446365600.008.png 446365600.009.png 446365600.010.png
Ciało rozszerzone
związek wielomianów z ciałami
¾ Zbiór wielomianów stopnia ( m-1 ) o współczynnikach
będących elementami ciała CG ( p ) tworzy ciało CG ( p m )z
liczbą wielomianów p m .
¾ Ogólnie ciało skończone CG ( p m )występuje dla dowolnej
liczby p m , przy czym, p jest liczbą pierwszą , a m -dodatnią
liczbą całkowitą.
¾ Ciało CG ( p )jest podciałem ciała CG ( p m ) w tym sensie, że
elementy ciała CG ( p ), są podzbiorem elementów ciała
CG ( p m ).⇒ Ciało CG ( p m ) jest rozszerzeniem ciała CG ( p ).
Robert Borowiec
Kodowanie i kryptografia
Wykład III, strona 5/30
Przykład ciała rozszerzonego
¾ Ciało rozszerzone CG(4) tworzy zbiór czterech
wielomianów stopnia pierwszego o
współczynnikach z ciała CG(2), tj: {0, 1, x, x+1}
¾ Dodawanie wielomianów polega na dodawaniu
ich współczynników w odpowiednim ciele, dla
danego przykładu CG(2)
¾ Mnożenie wielomianów polega na określeniu
reszty z podziału iloczynu przez wielomian
pierwszy, dla danego przykładu p ( x )= x 2 + x +1
Robert Borowiec
Kodowanie i kryptografia
Wykład III, strona 6/30
446365600.011.png 446365600.012.png 446365600.013.png 446365600.014.png 446365600.015.png 446365600.016.png 446365600.017.png
Przykład ciała rozszerzonego
Tablice dodawania i mnożenia w ciele CG(4)= CG(2 2 )
+
0
1
x
x+1
•
0
1
x
x+1
0
0
1
x
x+1
0
0
0
0
0
1
1
0
x+1
x
1
0
1
x
x+1
x
x
x+1
0
1
x
0
x
x+1
1
x+1
x+1
x
1
0
x+1
0
x+1
1
x
Robert Borowiec
* x
Kodowanie i kryptografia
Wykład III, strona 7/30
Element pierwotny
tworzenie ciał rozszerzonych
¾ W każdym ciele Galoisa istnieje co najmniej jeden element
pierwotny , oznaczany przez α.
¾ Element pierwotny charakteryzuje się tym, że jego potęgi
reprezentują wszystkie elementy ciała z wyjątkiem zera.
¾ Przykłady
CG(5): α=2, α 2 =4, α 3 =3, α 4 =1, więc α=2 jest
elementem pierwotnym ciała prostego CG(5)
CG(5): α=3, α 2 =4, α 3 =2, α 4 =1, więc α=3 jest też
elementem pierwotnym ciała prostego CG(5)
CG(4): α=x, α 2 =x+1, α 3 =α 0 =1, więc α=x jest
elementem pierwotnym ciała rozszerzonego
CG(2 2 )
Robert Borowiec
* x
Kodowanie i kryptografia
Wykład III, strona 8/30
446365600.018.png 446365600.019.png 446365600.020.png 446365600.021.png 446365600.022.png 446365600.023.png 446365600.024.png
Wielomian pierwotny
tworzenie ciał rozszerzonych
Wielomian p(x) stopnia m o współczynnikach z ciała
podstawowego CG(p) , którego pierwiastkiem jest element
pierwotny α nazywamy wielomianem pierwotnym . W
tablicy na następnym slajdzie pokazano wielomiany
pierwotne stopnia od 2 do 25 o współczynnikach z ciała
CG(2). Wielomiany te umożliwiają konstrukcję ciał
rozszerzonych od CG (2 2 ) do CG (2 25 ).
Przykład:
Element pierwotny α =x, a więc według tablicy α 2 =x+ 1
to: p(x)=x 2 +x+ 1⇒ p( α )= α 2 + α + 1= x+ 1+x+1=0, a więc
α jest pierwiastkiem p(x)
Robert Borowiec
Kodowanie i kryptografia
Wykład III, strona 9/30
Wielomiany pierwotne
Wielomiany pierwotne o współczynnikach z ciała CG(2)
Stopień
Wielomian
Stopień
Wielomian
Stopień
Wielomian
2
x 2 + x + 1
10
x 10 + x 3 + 1
18
x 18 + x 7 + 1
3
x 3 + x + 1
11
x 11 + x 2 + 1
19
x 19 +x 5 +x 2 +x+1
4
x 4 + x + 1
12
x 12 +x 6 +x 4 +x+1
20
x 20 + x 3 + 1
5
x 5 + x 2 + 1
13
x 13 +x 4 +x 3 +x+1
21
x 21 + x 2 + 1
6
x 6 + x + 1
14
x 14 +x 10 +x 6 +x+1
22
x 22 + x + 1
7
x 7 + x 3 + 1
15
x 15 + x + 1
23
x 23 + x 5 + 1
8
x 8 +x 4 +x 3 +x 2 +1
16
x 16 +x 12 +x 3 +x+1
24
x 24 +x 7 +x 2 +x+1
9
x 9 + x 4 + 1
17
x 17 + x 3 + 1
25
x 25 + x 3 + 1
Robert Borowiec
Kodowanie i kryptografia
Wykład III, strona 10/30
446365600.025.png 446365600.026.png 446365600.027.png 446365600.028.png 446365600.029.png 446365600.030.png 446365600.031.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin