Laboratorium ochrony danych



Pobieranie 211,85 Kb.
Strona1/3
Data14.02.2018
Rozmiar211,85 Kb.
  1   2   3

Laboratorium ochrony danych


Ćwiczenie nr 1




Temat ćwiczenia: Ciała skończone proste
Cel dydaktyczny: Poznanie metod generowania ciał skończonych prostych oraz zasad rachowa­nia w tych systemach algebraicznych, badanie właściwości ciał i wielomianów nad ciałami.

Wprowadzenie teoretyczne


W kryptografii oraz w technice kodowania stosuje się alfabety o skończonej liczbie elementów. Z reguły liczba elementów stosowanego alfabetu równa jest albo liczbie pierwszej, albo potędze liczby pierwszej. Dzięki temu zastosowany alfabet można uważać za strukturę algebraiczną, która nazywa się ciałem skończonym lub inaczej ciałem Galois.



Ciało skończone GF(p) jest to system algebraiczny, złożony ze zbioru liczb A={0,1,...,p-1} oraz z operacji dodawania i mnożenia modulo p, które można wykonywać na tych liczbach. Taki system spełnia wszystkie aksjomaty ciał, tzn.:

  • zbiór {0,1,...,p-1} wraz z operacją dodawania modulo p jest przemienną grupą addytywną, z elementem neutralnym 0,

  • zbiór {0,1,...,p-1} wraz z operacją mnożenia modulo p jest przemienną grupą multyplikatywną, z elementem neutralnym 1,

  • mnożenie jest rozdzielne względem dodawania, czyli dla każdego a, b i c należących do {0,1,..., p-1} spełniona jest zależnośc .

Skończone ciała proste można skonstruować dla zbiorów liczbowych o liczbie elementów równej liczbie pierwszej p. Ciała takie oznaczamy symbolem GF(p). Elementami ciała prostego są liczby: 0, 1, 2, ..., p1. Działania w ciałach prostych są takie same jak działania arytmetyczne z operacją modulo p. Ciało proste jest więc ciałem reszt modulo p. Sumę S i iloczyn P dwóch elementów ciała prostego a i b określają zależności:



W GF(p) każdy element ma element do siebie przeciwny, a każdy element niezerowy ma multyplikatywną odwrotność, dzięki czemu w ciele p-elementowym można też odejmować, dzielić, potęgować i wyciągać pierwiastki. Wobec tego nad ciałem GF(p) mają sens takie obliczenia, jak rozwiązywanie rownań liniowych i nieliniowych, dodawanie, mnożenie i odwracanie macierzy, wszystkie operacje na wielomianach, itp.

Element przeciwny ciała obliczamy za pomocą aksjomatu

,

a element odwrotny ciała obliczamy za pomocą aksjomatu



.

Jako przykład wieloelementowego skończonego ciała prostego przyjmijmy ciało GF(7). Elementami ciała GF(7) są liczby: 0, 1, 2, 3, 4, 5, 6.



Tabliczki dodawania i mnożenia ciała GF(7)

+

0

1

2

3

4

5

6






0

1

2

3

4

5

6

0

0

1

2

3

4

5

6




0

0

0

0

0

0

0

0

1

1

2

3

4

5

6

0




1

0

1

2

3

4

5

6

2

2

3

4

5

6

0

1




2

0

2

4

6

1

3

5

3

3

4

5

6

0

1

2




3

0

3

6

2

5

1

4

4

4

5

6

0

1

2

3




4

0

4

1

5

2

6

3

5

5

6

0

1

2

3

4




5

0

5

3

1

6

4

2

6

6

0

1

2

3

4

5




6

0

6

5

4

3

2

1


Do badania ciał skończonych używa się funkcji Eulera. Funkcja Eulera określa liczbę liczb naturalnych w zbiorze {1, 2, ..., n1} względnie pierwszych z n. Na przykład gdyż w zbiorze liczb mniejszych od 8 tylko 1, 3, 5 i 7 są względnie pierwsze z 8. Liczby względnie pierwsze nie mają żadnego wspólnego podzielnika oprócz 1. Funkcja Eulera dla liczby pierwszej p jest równa , gdyż wszystkie liczby mniejsze od p są względnie pierwsze z p.

Aby znaleźć wartość funkcji Eulera liczby złożonej n, rozkładamy ją na iloczyn potęg liczb pierwszych



Wartość funkcji Eulera dla takiej liczby złożonej wylicza się ze wzoru



.
P r z y k ł a d .

Obliczenie funkcji Eulera liczby złożonej.



n = 2646 = 23372, (2646) = 132276 = 756.
Niezerowe elementy ciała charakteryzuje rząd multyplikatywny. Rzędem multyplikatywnym dowolnego elementu ciała a jest najmniejsza liczba całkowita e taka, że

Na przykład rzędem multyplikatywnym elementu 5 ciała GF(7) jest 6, ponieważ 56=1


(
mod 7). Rząd mutyplikatywny elementu ciała GF(p) jest dzielnikiem .

Elementy ciała GF(7) mają następujące rzędy multyplikatywne:

element 1  rząd multyplikatywny 1,

elementy 2 i 4  rząd multyplikatywny 3,

elementy 3 i 5  rząd multyplikatywny 6,

element 6  rząd multyplikatywny 2.

Elementy ciała GF(p) mające rząd multyplikatywny równy nazywamy elementami pierwotnymi ciała. Liczbę elementów pierwotnych n ciała GF(p) można określić z zależności

gdzie jest funkcją Eulera.

Każdy element niezerowy ciała generuje grupę cykliczną. Element pierwotny ciała generuje grupę multyplikatywną ciała. W tak utworzonej grupie będą wszystkie niezerowe elementy ciała. Elementy grupy multyplikatywnej o rzędzie multyplikatywnym większym od 1 i mniejszym od generują podgrupy multyplikatywne. Taka podgrupa zachowuje działania grupy.

Grupę cykliczną generowaną przez dowolny element ciała skończonego otrzymamy, biorąc kolejne potęgi tego elementu. Na przykkład element 5 ciała GF(7) generuje grupę multyplikatywną: 5, 4, 6, 2, 3, 1, gdyż kolejne potęgi elementu 5 wynoszą: 5, 55=4, 45=6, 65=2, 25=3, 35=1. Podobnie element 2 generuje podgrupę trzyelementową: 2, 4, 1.



W teorii kodowania są szeroko wykorzystywane wielomiany nad ciałami skończonymi. Wielomian stopnia m nad ciałem GF(q) ma ogólną postać


Przyrównując ten wielomian do zera, otrzymamy


Zależność rekurencyjna stowarzyszona z tym wielomianem będzie



Działania należy tu wykonywać zgodnie z zasadami rachowania w ciele GF(q). Gdy założymy ciąg początkowy o długości m elementów: wówczas dla kolejnych wartości j można obliczyć z powyższej zależności elementy sekwencji okresowej. Okres wygenerowanej sekwencji okresowej zależy od typu wielomianu. W przypadku wielomianów pierwotnych sekwencja osiąga okres maksymalny. Okres maksymalny M dla wielomianu stopnia m nad ciałem GF(q) wynosi



M =

Wielomiany niepierwotne generują sekwencje o okresie mniejszym od M.

Niech wielomianem generującym sekwencję okresową będzie wielomian stopnia trzeciego nad ciałem GF(2)

Zależność rekurencyjna stowarzyszona z tym wielomianem ma postać



a wygenerowana sekwencja będzie: 1001011 1001011 ... .


Realizację zależności rekurencyjnej za pomocą układów logicznych pokazano na rysunku.

Generator binarnej sekwencji okresowej





  1   2   3


©operacji.org 2017
wyślij wiadomość

    Strona główna