13. BAIGTINIU_{‘} KŪNU_{‘} ELEMENTU_{‘} REIŠKIMAS

Yra keletas baigtiniu_{‘} kūnu_{‘} elementu_{‘} reiškimo būdu_{‘}. Pirmasis iš ju_{‘} remiasi tuo, kad faktoržiedis GF (q)[x]/(f(x)), kai f(x) yra neredukuojamas polinomas virš GF (q), – kūnas. Antrasis – kad baigtinio kūno GF (q) multiplikacinė grupė GF (q)^{∗} yra ciklinė ir kiekvienas nenulinis šio kūno elementas yra primityviojo elemento laipsnis. Pirmuoju atveju kūno elementai – tai polinomai virš GF (q) ir todėl sudėties veiksmas šiems elementams atliekamas labai paprastai, o štai sandaugai suskaičiuoti reikia daug darbo. Antruoju atveju – viskas atvirkščiai: sandaugos veiksmas ciklinės grupės elementams – tai paprasčiausi veiksmai su laipsnio rodikliais, o štai šiu_{‘} elementu_{‘} sudėtis reikalauja nemažai skaičiavimu_{‘}. Laimei, yra glaudus abieju_{‘} reiškimo būdu_{‘} ryšys, pateikiamas indeksu_{‘} lentele. Pateiksime ir trečia_{‘}ji_{‘} baigtinio kūno elementu_{‘} reiškimo būda_{‘}, jungianti_{‘} pirmu_{‘}ju_{‘} dvieju_{‘} tiek teigiamas, tiek neigiamas savybes.

1. Tegu GF (q), q = p^{n} yra baigtinis kūnas, p – pirminis. Tada egzistuoja (žr. 9.7 teigini_{‘}) neredukuojamas virš GF (p) n-ojo laipsnio polinomas f(x) ir

GF (q) = GF (p)[x]/(f(x)) = {r(x) + (f(x)) | deg r(x) < n}.

Šiuo atveju kūno GF (q) elementus tapatiname su ne aukštesnio negu n − 1 laipsnio polinomais virš GF (p), o abi operacijos su šiais polinomais atliekamos mod f(x).

Tegu a yra polinomo f(x) šaknis kuriame nors kūno GF (p) plėtinyje. Iš 8.11 teiginio žinome, kad GF (q) yra izomorfiškas (GF (p))(a) ir todėl

GF (q) = {r(a) | r(x) ∈ GF (p)[x], f(a) = 0}.

10.1 pavyzdys. Norint užrašyti kūno GF (16) = GF (2^{4}) elementus, prireiks neredukuojamo virš GF (2) ketvirtojo laipsnio polinomo. Visus tokius polinomus galima rasti išbraukus iš visu_{‘} 4-ojo laipsnio polinomu_{‘} virš GF (2) sa_{‘}rašo redukuojamus polinomus. Iš viso 4-ojo laipsnio polinomu_{‘} virš GF (2) yra 2^{4} = 16.

Redukuojamieji polinomai f(x) = αx^{4} + βx^{3} + γx^{2} + δx + e, α, β, γ, δ, e ∈ GF (2), yra vieno iš pavidalu_{‘}

f(x) = (α_{0} + α_{1}x + α_{2}x^{2} + 1 · x^{3})(β_{0} + x),
f(x) = (γ_{0} + γ_{1}x + x^{2})(δ_{0} + δ_{1}x + x^{2}),
α_{0}, α_{1}, α_{2}, β_{0}, γ_{0}, γ_{1}, δ_{0}, δ_{1} ∈ GF (2) = {0, 1}.

Kai e = 0, t.y. bent vienas elementas iš poru_{‘} α_{0}, α_{1} arba γ_{0}, γ_{1} lygus nuliui, tai polinomas f(x) yra redukuojamas. Tegu dabar α_{0}, α_{1}, γ_{0}, γ_{1} – nenuliniai elementai.

Sudaugine_{‘} polinomus

(x^{3} + 1)(x + 1) = x^{4} + x^{3} + x + 1,
(x^{3} + x + 1)(x + 1) = x^{4} + x^{3} + x^{2} + 1,
(x^{3} + x^{2} + 1)(x + 1) = x^{4} + x^{2} + x + 1,
(x^{3} + x^{2} + x + 1)(x + 1) = x^{4} + 1,
(x^{2} + 1)(x^{2} + 1) = x^{4} + 1,
(x^{2} + 1)(x^{2} + x + 1) = x^{4} + x^{3} + x + 1,
(x^{2} + x + 1)(x^{2} + x + 1) = x^{4} + x^{2} + 1,

matome, kad tik trys polinomai f_{1}(x) = x^{4} + x + 1, f_{2}(x) = x^{4} + x^{3} + 1 ir f_{3}(x) = x^{4} + x^{3} + x^{2} + x + 1 yra neredukuojami virš GF (2).

Pasirinkime viena_{‘} iš ju_{‘}, pavyzdžiui, f(x) = x^{4} + x^{3} + 1. Tada

GF (2)[x]/(x_{4} + x_{3} + 1) = GF (16) = (GF (2))(a);

čia a – polinomo f(x) šaknis. Išvardysime šio kūno elementus. Konstantos: 0, 1. Tiesiniai elementai: a, a + 1. Kvadratiniai elementai: a^{2}, a^{2} + 1, a^{2} + a, a^{2} + a + 1. Kubiniai elementai: a^{3}, a^{3} + 1, a^{3} + a, a^{3} + a + 1, a^{3} + a^{2}, a^{3} + a^{2} + 1,

a^{3} + a^{2} + a, a^{3} + a^{2} + a + 1.

Taip išreikštu_{‘} kūno GF (16) elementu_{‘} sudėtis – tai ne didesnio kaip 3-ojo laipsnio polinomu_{‘} sudėtis virš GF (2). Pavyzdžiui,

(a^{3} + a + 1) + (a^{2} + a) = a^{3} + a^{2} + 1 (2 = 0).

Dauginti kūno GF (16)elementus sunkiau, nes visa_{‘} laika_{‘} reikia atsižvelgti i_{‘} tai, kad f(a) = a^{4} + a^{3} + 1 = 0, t.y. a^{4} = a^{3} + 1 (−1 = 1 kūne GF (2)). Pavyzdžiui,

a^{7} = a^{4} · a^{3} = (a^{3} + 1)a^{3} = a^{6} + a^{3} = a^{4} · a^{2} + a^{3}

= (a^{3} + 1)a^{2} + a^{3} = a^{5} + a^{2} + a^{3} = a^{4}a + a^{2} + a^{3}

= (a^{3} + 1)a + a^{2} + a^{3} = a^{4} + a + a^{2} + a^{3} = a^{3} + 1 + a + a^{2} + a^{3}

= 1 + a + a^{2}.

2. Tegu a yra primityvusis kūno GF (q) elementas. Tada

GF (q) = {0, 1 = a^{0}, a, …, a^{q−2}}.

Dvieju_{‘} taip išreikštu_{‘} kūno GF (q) elementu_{‘} sandauga apibrėžta lygybe

a^{r} · a^{s} = a^{r+s (mod q−1)}.

Šiu_{‘} elementu_{‘} sudėtis apibrėžiama primityviajam elementui a parenkant minimalu_{‘}ji_{‘} polinoma_{‘} m(x) ir kiekvienam a laipsniui priskiriant vieninteli_{‘} elementa_{‘}

α_{0} + α_{1}a + … + α_{n−1}a^{n−1}, n = deg m(x).

Tada elementu_{‘} sudėtis apibrėžiama kaip 10.1 pavyzdyje.

10.2 pavyzdys. Tegu f(x) = x^{4} + x^{3} + 1, kaip ir 10.1 pavyzdyje, neredukuojamas polinomas virš GF (2). Tegu a – polinomo f(x) šaknis. Elemento a eilė ord_{GF (16)^{∗}}(a) kūno GF (16) multiplikacinėje grupėje yra lygi grupės GF (16)^{∗} eilės |GF (16)^{∗}| = 16 − 1 = 15 dalikliui. Taigi

a^{1} ≠ 1,
a^{3} ≠ 1,
a^{5} = a^{4} · a = (a^{3} + 1)a = a^{4} + a = a^{3} + a + 1 ≠ 1,

todėl a^{15} = 1 ir ord_{GF (16)^{∗}}(a) = 15, t.y. a – primityvusis kūno GF (16) elementas. Tad

GF (16) = {0, 1, a, a^{2}, …, a^{13}, a^{14}}.

Dvieju_{‘} kūno GF (16) elementu_{‘} reiškimo būdu_{‘} ryšys pateikiamas vadinama_{‘}ja indeksu_{‘} lentele, kurioje kiekvienam kūno GF (16) primityviojo elemento a laipsniui a^{k} priskiriamas šio kūno elementas, išreikštas polinomu. Pavyzdžiui,

a^{4} = a^{3} + 1,

a^{5} = a^{4} · a = (a^{3} + 1)a = a^{4} + a = a^{3} + a + 1,

a^{6} = a^{5} · a = (a^{3} + a + 1)a = a^{4} + a^{2} + a = a^{3} + a^{2} + a + 1 ir t. t.

Indeksas  Laipsninis  Polinominis  Vektorinis
reiškimas  reiškimas  reiškimas
∗  0  0  (0, 0, 0, 0)
0  1  1  (0, 0, 0, 1)
1  a  a  (0, 0, 1, 0)
2  a^{2}  a^{2}  (0, 1, 0, 0)
3  a^{3}  a^{3}  (1, 0, 0, 0)
4  a^{4}  a^{3} + 1  (1, 0, 0, 1)
5  a^{5}  a^{3} + a + 1  (1, 0, 1, 1)
6  a^{6}  a^{3} + a^{2} + a + 1  (1, 1, 1, 1)
7  a^{7}  a^{2} + a + 1  (0, 1, 1, 1)
8  a^{8}  a^{3} + a^{2} + a  (1, 1, 1, 0)
9  a^{9}  a^{2} + 1  (0, 1, 0, 1)
10  a^{10}  a^{3} + a  (1, 0, 1, 0)
11  a^{11}  a^{3} + a^{2} + 1  (1, 1, 0, 1)
12  a^{12}  a + 1  (0, 0, 1, 1)
13  a^{13}  a^{2} + a  (0, 1, 1, 0)
14  a^{14}  a^{3} + a^{2}  (1, 1, 0, 0)

Pastabos. 1. Neišskiriant 0, paprastai žymima a^{∗} = 0, a ∈ GF (q).

2. Iš paskutinio stulpelio matome, kad kūnas GF (16) yra 4-matė vektorinė erdvė virš GF (2), kurios bazė {1, a, a^{2}, a^{3}}, ir todėl šiame stulpelyje yra mūsu_{‘} vektorinės erdvės elementu_{‘} koordinatės nurodytoje bazėje.

Operacijas kūne GF (16) iliustruosime pavyzdžiu:

(a^{10} + a^{7} + a^{5} + a^{2} + 1)(a^{4} + a^{3} + a)
= a^{14} + a^{11} + a^{9} + a^{6} + a^{4} + a^{13} + a^{10}
+ a^{8} + a^{5} + a^{3} + a^{11} + a^{8} + a^{6} + a^{3} + a
= a^{14} + a^{13} + a^{10} + a^{9} + a^{5} + a^{4} + a
= (1, 1, 0, 0) + (0, 1, 1, 0) + (1, 0, 1, 0) + (0, 1, 0, 1)
+ (1, 0, 1, 1) + (1, 0, 0, 1) + (0, 0, 1, 0) =
= (0, 1, 0, 1) = a^{9} = a^{2} + 1.

10.3 apibrėžimas. Primityviojo kūno GF (q) elemento minimalusis polinomas vadinamas primityviuoju polinomu.

Primityvieji polinomai yra svarbūs, nes ju_{‘} šaknu_{‘} laipsniais reiškiami baigtinio kūno elementai. Tačiau šiu_{‘} polinomu_{‘} paieška nėra paprasta ir ja_{‘} aptarsime vėliau.

3. Trečias baigtinio kūno GF (q) elementu_{‘} reiškimo būdas – matricos. Naudojamasi tiesinės algebros teiginiu apie tai, kad bet kurio poli-

nomo f(x) = α_{0} + α_{1}x + … + α_{n−1}x^{n−1} + x^{n} (čia α_{i} – kūno K elementai) lydinčioji matrica

A = ( \begin{matrix}0 & 0 & … & 0 & −α_{0} \\ 1 & 0 & … & 0 & −α_{1} \\ 0 & 1 & … & 0 & −α_{2} \\ … & … & … & … & … \\ 0 & 0 & … & 1 & −α_{n−1} \end{matrix} )

yra polinomo f(x) šaknis: f(A) = α_{0}I + α_{1}A + … + α_{n−1}A^{n−1} + A^{n} = 0.

Taigi turėdami n-ojo laipsnio neredukuojama_{‘} polinoma_{‘} f(x) virš kūno GF (q), kurio lydinčioji matrica yra A, kūno GF (q^{n}) elementus galime vaizduoti matricomis

β_{0}I + β_{1}A + … + β_{n−1}A^{n−1}, β_{0}, β_{1}, …, β_{n} ∈ GF (q).

Svarbiausia, kad kūno elementu_{‘} aritmetika_{‘} galima suvesti i_{‘} matricu_{‘} aritmetika_{‘}, nepriklausomai nuo to, ar neredukuojamas f(x) yra primityvusis, ar ne.

10.4 pavyzdys. Polinomas f(x) = x^{2} + 1 yra neredukuojamas virš GF (3) (nes neturi virš GF (3) šaknu_{‘}). Šio polinomo lydinčioji matrica yra

A = ( \begin{matrix}0 & 2 \\ 1 & 0 \end{matrix} ) .

GF (9) = (GF (3))(A)

= \{0 = ( \begin{matrix}0 & 0 \\ 0 & 0 \end{matrix} ) , I = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) , 2I = ( \begin{matrix}2 & 0 \\ 0 & 2 \end{matrix} ) ,

A = ( \begin{matrix}0 & 2 \\ 1 & 0 \end{matrix} ) , A + I = ( \begin{matrix}1 & 2 \\ 1 & 1 \end{matrix} ) , A + 2I = ( \begin{matrix}2 & 2 \\ 1 & 2 \end{matrix} ) ,

2A = ( \begin{matrix}0 & 1 \\ 2 & 0 \end{matrix} ) , 2A + I = ( \begin{matrix}1 & 1 \\ 2 & 1 \end{matrix} ) , 2A + 2I = ( \begin{matrix}2 & 1 \\ 2 & 2 \end{matrix} ) \}.

Operacijas iliustruosime pavyzdžiu:

(2A + 2I)(A + 2I) = ( \begin{matrix}2 & 1 \\ 2 & 2 \end{matrix} ) · ( \begin{matrix}2 & 2 \\ 1 & 2 \end{matrix} ) = ( \begin{matrix}2 & 0 \\ 0 & 2 \end{matrix} ) = 2I.

10.5 pavyzdys. Neredukuojamas virš GF (3) polinomas f(x) = x^{2} + 2x + 2 yra primityvusis polinomas, nes, kai a^{2} + 2a + 2 = 0 (čia a yra f(x) šaknis),

a^{2} = −2a − 2 = a + 1 ≠ 1,
a^{4} = a^{2} + 2a + 1 = 3a + 2 = 2 ≠ 1,
a^{8} = 4 = 1,
ord_{GF (9)^{∗}}(a) = |GF (9)^{∗}|.

Primityviojo polinomo f(x) lydinčioji matrica yra

C = ( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ) .

Tada

GF (9) = \{0 = ( \begin{matrix}0 & 0 \\ 0 & 0 \end{matrix} ) , C = ( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ) , C^{2} = ( \begin{matrix}1 & 1 \\ 1 & 2 \end{matrix} ) ,

C^{3} = ( \begin{matrix}1 & 2 \\ 2 & 0 \end{matrix} ) , C^{4} = ( \begin{matrix}2 & 0 \\ 0 & 2 \end{matrix} ) , C^{5} = ( \begin{matrix}0 & 2 \\ 2 & 2 \end{matrix} ) ,

C^{6} = ( \begin{matrix}2 & 2 \\ 2 & 1 \end{matrix} ) , C^{7} = ( \begin{matrix}2 & 1 \\ 1 & 0 \end{matrix} ) , C^{8} = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) \}.

Operacijas iliustruosime pavyzdžiu:

(C^{7} + 2C^{4})(C^{3} + C) = ( ( \begin{matrix}2 & 1 \\ 1 & 0 \end{matrix} ) + 2 ( \begin{matrix}2 & 0 \\ 0 & 2 \end{matrix} ) )

· ( ( \begin{matrix}1 & 2 \\ 2 & 0 \end{matrix} ) + ( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ) )

= ( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ) · ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ) = C.

Pastaba. Nors kūno elementus išreiškus matricomis operacijas atlikti paprasta, kai deg f(x) yra didelis, tenka naudoti didelio matavimo matricas.