Kodowanie i kryptografia
Algebra 2
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki
pokój 908, C-5
tel. [phone]
Wykład III
e-mail: [e-mail]
www: lstwww.ita.pwr.wroc.pl/~RB/
2-godziny
Wielomiany
Zdefiniujemy przekształcenie
n-1
F(a) a"
"a xi
i
i=0
które ciągowi a=(an-1, an-2 ,..., a1 , a0) przyporządkowuje, w
sposób wzajemnie jednoznaczny, wielomian
a(x)= an-1xn-1 + an-2xn-2 + Å"Å"Å" + a1x1 + a0x0
Przykłady:
111 Ô! x2+x+1; 101 Ô! x2+1; 001 Ô! 1; 100Ô! x2
Kodowanie i kryptografia
Robert Borowiec

Wykład III, strona 2/30
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
Kodowanie i kryptografia
Robert Borowiec
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
c(x) = Rp(x) a(x)b(x)
[ ]
Wielomian p(x) musi być wielomianem pierwszym, tzn.
wielomianem nie rozkładalnym w ciele CG(p)
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 4/30
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(pm) z
liczbą wielomianów pm .
Ogólnie ciało skończone CG(pm) występuje dla dowolnej
liczby pm , przy czym, p jest liczbÄ… pierwszÄ…, a m-dodatniÄ…
liczbą całkowitą.
Ciało CG(p) jest podciałem ciała CG(pm) w tym sensie, że
elementy ciała CG(p), są podzbiorem elementów ciała
CG(pm).Ò! CiaÅ‚o CG(pm) jest rozszerzeniem ciaÅ‚a CG(p).
Kodowanie i kryptografia
Robert Borowiec
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)=x2+x+1
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 6/30
Przykład ciała rozszerzonego
Tablice dodawania i mnożenia w ciele CG(4)= CG(22)
+ 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
Kodowanie i kryptografia
Robert Borowiec

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(22)
Kodowanie i kryptografia
Robert Borowiec

Wykład III, strona 8/30
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(22) do CG(225).
Przykład:
Element pierwotny ą=x, a więc według tablicy ą2=x+1
to: p(x)=x2+x+1Ò! p(Ä…)= Ä…2 + Ä… + 1= x+1+x+1=0, a wiÄ™c
Ä… jest pierwiastkiem p(x)
Kodowanie i kryptografia
Robert Borowiec
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 x2 + x + 1 10 x10 + x3 + 1 18 x18 + x7 + 1
3 x3 + x + 1 11 x11 + x2 + 1 19 x19+x5+x2+x+1
4 x4 + x + 1 12 x12+x6+x4+x+1 20 x20 + x3 + 1
5 x5 + x2 + 1 13 x13+x4+x3+x+1 21 x21 + x2 + 1
6 x6 + x + 1 14 x14+x10+x6+x+1 22 x22 + x + 1
7 x7 + x3 + 1 15 x15 + x + 1 23 x23 + x5 + 1
8 x8+x4+x3+x2+1 16 x16+x12+x3+x+1 24 x24+x7+x2+x+1
9 x9 + x4 + 1 17 x17 + x3 + 1 25 x25 + x3 + 1
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 10/30
Ciała rozszerzone
różne reprezentacje elementów ciała rozszerzonego
Elementy ciała rozszerzonego CG(4)
Reprezentacja Reprezentacja Reprezentacja
wielomianowa binarna potęgowa
0 00 Nie istnieje
1 01 Ä…0
x 10 Ä…1
x+1 11 Ä…2
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 11/30
Przykład ciała rozszerzonego
przedstawienie za pomocÄ… elementu pierwotnego
Tablice dodawania i mnożenia w ciele CG(4)
+ 0 1 Ä… Ä…2
" 0 1 Ä… Ä…2
0 0 Ä…0 Ä… Ä…2
0 0 0 0 0
1 Ä…0 0 Ä…2 Ä…
1 0 Ä…0 Ä… Ä…2
Ä… Ä… Ä…2 0 Ä…0
Ä… 0 Ä… Ä…2 Ä…0
Ä…2 Ä…2 Ä… Ä…0 0
Ä…2 0 Ä…2 Ä…0 Ä…
Kodowanie i kryptografia
Robert Borowiec

Wykład III, strona 12/30
Tworzenie ciała rozszerzonego
Przyjmujemy element pierwotny Ä…=x,
Wybieramy wielomian pierwotny p(x)
stopnia m o współczynnikach z ciała
podstawowego CG(p)
Obliczamy wszystkie elementy ciała
rozszerzonego, poprzez wyznaczenie
kolejnych potęg elementu pierwotnego ąi,
gdzie i =0,..., q-2, a q=pm
Budujemy tablice dodawania i mnożenia
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 13/30
Tworzenie ciała rozszerzonego
na przykładzie ciała CG (pm)=CG(8), p=2, m=3
Przyjmujemy element pierwotny Ä…=x,
Wybieramy wielomian pierwotny p(x) stopnia 3 z
tabeli*: p(x)=x3+x+1
q=23=8 Ò! q-2=6
Ò! elementy ciaÅ‚a: Ä…0 , Ä…1 , Ä…2 , Ä…3 , Ä…4 , Ä…5 , Ä…6 , Ä…7 =Ä…0
Ò! UzupeÅ‚niamy o element zerowy, 0
* -UWAGA! W przedstawionej wcześniej tabeli są
zamieszone wielomiany pierwotne tylko do budowy
ciała rozszerzonego na bazie ciała prostego CG(2).
Jeżeli p`"2 to należy znalez
ć odpowiednie
wielomiany.
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 14/30
Tworzenie ciała rozszerzonego
Tablica 5. Elementy ciała CG(8) generowane przez wielomian:
p(x)=x3+x+1
Reprezentacja Reprezentacja Reprezentacja
potęgowa wielomianowa binarna
Nie istnieje 0 000
x0 mod p(x) Ò! 1 001
Ä…0=Ä…7
Ä…1 x1 mod p(x) Ò! x 010
Ä…2 x2 mod p(x) Ò! x2 100
Ä…3 x3 mod p(x) Ò! x+1 011
Ä…4 x4 mod p(x) Ò! x2+x 110
Ä…5 x5 mod p(x) Ò! x2+ x+1 111
Ä…6 x6 mod p(x) Ò! x2+1 101
Kodowanie i kryptografia
Robert Borowiec

Wykład III, strona 15/30
Tworzenie ciała rozszerzonego
Budowa tabliczek mnożenia i dodawania
Dodanie dwóch elementów ciała wymaga dodania w ciele
pierwotnym (w naszym przypadku CG(2) )
współczynników przy odpowiednich potęgach x, na
przykład:
Ä…3+Ä…2= (x+1) + x2=x2+ x+1= Ä…5
Mnożenie dwóch elementów sprowadza się do sumowania
(modulo q-1) wykładników potęg elementu pierwotnego,
na przykład:
Ä…5·Ä…6= Ä…(5+6) mod 7= Ä…11 mod 7 = Ä…7·Ä…4 = Ä…4
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 16/30
Tworzenie ciała rozszerzonego
Tablica 5. Tabliczka dodawania ciała CG(8)
+ 0 Ä…0 Ä…1 Ä…2 Ä…3 Ä…4 Ä…5 Ä…6
0 0 Ä…0 Ä…1 Ä…2 Ä…3 Ä…4 Ä…5 Ä…6
Ä…0 Ä…0 0 Ä…3 Ä…6 Ä…1 Ä…5 Ä…4 Ä…2
Ä…1 Ä…1 Ä…3 0 Ä…4 Ä…0 Ä…2 Ä…6 Ä…5
Ä…2 Ä…2 Ä…6 Ä…4 0 Ä…5 Ä…1 Ä…3 Ä…0
Ä…3 Ä…3 Ä…1 Ä…0 Ä…5 0 Ä…6 Ä…2 Ä…4
Ä…4 Ä…4 Ä…5 Ä…2 Ä…1 Ä…6 0 Ä…0 Ä…3
Ä…5 Ä…5 Ä…4 Ä…6 Ä…3 Ä…2 Ä…0 0 Ä…1
Ä…6 Ä…6 Ä…2 Ä…5 Ä…0 Ä…4 Ä…3 Ä…1 0
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 17/30
Tworzenie ciała rozszerzonego
Tablica 6. Tabliczka mnożenia ciała CG(8)
" 0 Ä…0 Ä…1 Ä…2 Ä…3 Ä…4 Ä…5 Ä…6
0 0 0 0 0 0 0 0 0
Ä…0 0 Ä…0 Ä…1 Ä…2 Ä…3 Ä…4 Ä…5 Ä…6
Ä…1 0 Ä…1 Ä…2 Ä…3 Ä…4 Ä…5 Ä…6 Ä…0
Ä…2 0 Ä…2 Ä…3 Ä…4 Ä…5 Ä…6 Ä…0 Ä…1
Ä…3 0 Ä…3 Ä…4 Ä…5 Ä…6 Ä…0 Ä…1 Ä…2
Ä…4 0 Ä…4 Ä…5 Ä…6 Ä…0 Ä…1 Ä…2 Ä…3
Ä…5 0 Ä…5 Ä…6 Ä…0 Ä…1 Ä…2 Ä…3 Ä…4
Ä…6 0 Ä…6 Ä…0 Ä…1 Ä…2 Ä…3 Ä…4 Ä…5
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 18/30
Inny przykład ciała rozszerzonego
Tablica 8. Elementy ciała CG(16)=CG(24) generowane przez
wielomian: p(x)=x4+x+1
Reprezentacja Reprezentacja Reprezentacja Reprezentacja
potęgowa wielomianowa potęgowa wielomianowa
Nie istnieje 0 Ä…7 x3 +x+1
1 Ä…8 x2+1
Ä…0=Ä…15
Ä…1 x Ä…9 x3+x
Ä…2 x2 Ä…10 x2+x+1
Ä…3 x3 Ä…11 x3+x2+x
Ä…4 x+1 Ä…12 x3+x2+x+1
Ä…5 x2+x Ä…13 x3+x2+1
Ä…6 x3+x2 Ä…14 x3 +1
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 19/30
Wielomiany
Pierwiastki wielomianu
Każdy wielomian f(x) stopnia n ma n
pierwiastków; jeśli wielomian f(x) jest wielomianem
nierozkładalnym nad pewnym ciałem, to wszystkie
jego pierwiastki są elementami ciała rozszerzonego.
Przykład
f (x) = x4 + x3 + x2 + x +1
Wielomian jest
wielomianem nierozkładalnym nad ciałem CG(2) i
nie ma pierwiastków w tym ciele; ma natomiast
cztery pierwiastki: ą3, ą6, ą9, ą12 z ciała
rozszerzonego CG(16)
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 20/30
Wielomiany
Pierwiastki wielomianu
Sprawdzenie, że ą3, ą6, ą9, ą12 z ciała rozszerzonego CG(16)
sÄ… pierwiastkami wielomianu f (x) = x4 + x3 + x2 + x +1
4 3 2
f (Ä…3)= (Ä…3) + (Ä…3) +(Ä…3) +Ä…3 +1 = Ä…12 +Ä…9 +Ä…6 +Ä…3 +1 =
= (x3 + x2 + x +1)+(x3 + x)+(x3 + x2)+(x3)+1 = 0
4 3 2
f (Ä…6)= (Ä…6) +(Ä…6) +(Ä…6) + Ä…6 +1 = Ä…9 + Ä…3 +Ä…12 +Ä…6 +1 = 0,
4 3 2
9 9 9 9 9 6 3 9
f = + + + Ä… +1 = Ä… + Ä…12 + Ä… + Ä… + 1 = 0,
(Ä… ) (Ä… ) (Ä… ) (Ä… )
4 3 2
f (Ä…12)= (Ä…12) +(Ä…12) +(Ä…12) +Ä…12 +1 = Ä…3 +Ä…6 +Ä…9 +Ä…12 +1 = 0,
x4 + x3 + x2 + x +1 = (x +Ä…3)(x + Ä…6)(x +Ä…9)(x +Ä…12)

Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 21/30
Wielomiany
Własności pierwiastków wielomianu
Niech f(x) będzie wielomianem stopnia n o współczynnikach
z ciaÅ‚a CG(2), nierozkÅ‚adalnym w tym ciele. Niech ² bÄ™dzie
pierwiastkiem tego wielomianu, to znaczy f(²) = 0. Ponieważ
f(x) jest wielomianem nierozkÅ‚adalnym nad ciaÅ‚em CG(2), to ²
musi być elementem pewnego ciała rozszerzonego CG(2m).
WÅ‚aÅ›ciwoÅ›ci elementu ² :
1. dla dowolnych l e" 0, ² 2 l jest także pierwiastkiem f(x).
" Elementy ² 2 l nazywamy elementami
sprzężonymi z elementem ² .
" Dla l>(m-1) elementy sprzężone powtarzają się.
Kodowanie i kryptografia
Robert Borowiec

Wykład III, strona 22/30
Wielomiany
Własności pierwiastków wielomianu cd..
2. JeÅ›li ² jest niezerowym elementem ciaÅ‚a CG(2m),
to ² 2 m-1 jest zawsze równe jednoÅ›ci, można wiÄ™c uÅ‚ożyć
równanie
2m -1
² +1 = 0
z którego wynika, że ² jest pierwiastkiem wielomianu
m
x2 -1 +1
nad ciałem CG(2). Jest to wielomian stopnia (2m-1),
ma więc (2m-1), pierwiastków będących niezerowymi
elementami ciała CG(2m).
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 23/30

Wielomiany
Własności pierwiastków wielomianu cd..
Zerowy element tego ciała jest pierwiastkiem
wielomianu (x). Elementy ciała CG(2m) tworzą więc
wszystkie pierwiastki wielomianu
m
(x2 + x)
Wielomian najniższego stopnia o współczynnikach z
ciaÅ‚a CG(2), którego pierwiastkiem jest element ²
ciała CG(2m) nazywamy wielomianem minimalnym
tego elementu.
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 24/30
Wielomiany
Wielomiany minimalne
Przykład
Na przykład wielomian szesnastego stopnia ,
określony nad ciałem CG(2), ma szesnaście
pierwiastków będących elementami ciała CG(24),
4
x2 +x =
= x(x+1)(x2 +x+1)(x4 +x+1)(x4 +x3 +1)(x4 +x3 +x2 +x+1)
Każdy czynnik w tym rozwinięciu jest wielomianem
( )
minimalnym Ȳ x nad ciałem CG(2) pewnego
elementu ² z ciaÅ‚a CG(24)
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 25/30
Wielomiany minimalne
Tablica 9. Wielomiany minimalne elementów ciała CG(24)
Pierwiastki Wielomian
sprzężone minimalny
0 x
Ä…0
x+1
Ä…1, Ä…2, Ä…4, Ä…8
x4+x+1
Ä…3, Ä…6, Ä…9, Ä…12
x4+x3+x2+x+1
Ä…5, Ä…10
x2+x+1
Ä…7, Ä…11, Ä…13, Ä…14
x4+x3+1
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 26/30
Wielomiany minimalne
Element ² i elementy z nim sprzężone
stanowią pełny zbiór pierwiastków wielomianu
minimalnego, więc wielomian minimalny elementu
można przedstawić w postaci
e-1
2i
(17)
È (x)= (x + ² ).
² "
i=0
gdzie e oznacza stopień wielomianu minimalnego; e
jest najmniejszą liczbą całkowitą spełniającą
równanie
e
(18)
²2 = ².
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 27/30
Wielomiany minimalne
przykład
Elementami sprzężonymi z elementem ² = Ä…3 w
ciele CG(24) sÄ…:
223
²2 = Ä…6, ²2 = Ä…12 , ² = Ä…9.
Wielomian minimalny elementu ² = Ä…3 w ciele
CG(24) z ciała obliczony z wzoru (17) ma postać
ÈÄ… (x)= (x +Ä…3)(x +Ä…6)(x + Ä…9)(x + Ä…12)=
3
= (x2 +Ä…2x + Ä…9)(x2 + Ä…8x + Ä…6)=
= x4 + x3 + x2 + x +1.
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 28/30
Wielomiany minimalne
Wielomian minimalny elementu pierwotnego
ciała CG(2m) ma stopień m i jest wielomianem
pierwotnym. Ciało Galoisa CG(2m) tworzymy
posługując się wielomianem pierwotnym p(x) stopnia
m i elementem pierwotnym ą, będącym
pierwiastkiem wielomianu p(x). Kolejne potęgi
elementu pierwotnego reprezentujÄ… wszystkie
niezerowe elementy ciała CG(2m) .
TworzÄ… one grupÄ™ multiplikatywnÄ… CG(2m-1).
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 29/30
KONIEC
Dziękuję za uwagę
Kodowanie i kryptografia
Robert Borowiec
Wykład III, strona 30/30