14. NEREDUKUOJAMU_{‘} POLINOMU_{‘} LAIPSNIS IR EILĖ

Neredukuojami polinomai baigtiniu_{‘} kūnu_{‘} teorijoje vaidina panašu_{‘} vaidmeni_{‘} kaip ir pirminiai skaičiai skaičiu_{‘} teorijoje. Dauguma konstruktyviu_{‘} uždaviniu_{‘} sprendimu_{‘} remiasi neredukuojamu_{‘} polinomu_{‘} savybėmis. Su keliomis iš šiu_{‘} savybiu_{‘} jau esame susipažine_{‘}:

1. Neredukuojamas virš GF (q) polinomas f(x) yra savo šaknies α minimalusis polinomas, I = {g(x) ∈ GF (q) [x] | g(α) = 0} = (f(x)), t.y. α yra polinomo g(x) ∈ GF (q) [x] šaknis tada ir tik tada, kai g(x) dalijasi iš f(x) (žr. 8.11 teigini_{‘}).

2. Bet kuriam natūraliajam skaičiui n virš bet kokio baigtinio kūno GF (q) egzistuoja neredukuojamas n-ojo laipsnio polinomas.

Dabar nustatysime kitas neredukuojamu_{‘} polinomu_{‘} savybes.

11.1 teiginys. Tegu f(x) ∈ GF (q) [x] yra neredukuojamas n-ojo laipsnio polinomas, o α – viena iš polinomo f(x) šaknu_{‘}, esanti kūno GF (q) plėtinyje. Tada polinomo f(x) skaidinio kūnas K yra (GF (q))(α) = GF (q^{n}).

I_{‘} rodymas. Iš 8.17 apibrėžimo žinome, kad polinomo f(x) skaidinio kūnas yra mažiausias kūno GF (q) plėtinys, kuriame yra visos polinomo f(x) šaknys. Todėl

GF (q) ⊆ (GF(q))(α) ⊆ K.

Kita vertus, [(GF (q))(α) : GF (q)] = n ir |(GF (q))(α)| = q^{n}. Remiantis 9.3 teiginio 1) dalimi, visi kūno (GF (q))(α) elementai yra polinomo f_{q^{n}}(x) = x^{q^{n}} − x šaknys. Taigi f_{q^{n}}(α) = α^{q^{n}} − α = 0 ir, remiantis 8.11 teiginiu, f_{q^{n}(x)} dalijasi iš f(x): visos polinomo f(x) šaknys yra ir polinomo f_{q^{n}}(x) šaknys. Todėl

K ⊆ (GF(q))(α)

ir

K = (GF (q))(α) = GF (q^{n}).

△

11.2 teiginys. Tegu f(x) ∈ GF (q) [x] neredukuojamas n-ojo laipsnio polinomas. Tada polinomas f_{q^{m}}(x) = x^{q^{m}} − x dalijasi iš f(x) tada ir tik tada, kai m dalijasi iš n.

I_{‘} rodymas. Jau žinome, kad polinomo f(x) skaidinio kūnas yra GF (q^{n}), o polinomo f_{q^{m}}(x) skaidinio kūnas yra GF (q^{m}). Be to, jei kūnas GF (q^{n}) yra kūno GF (q^{m}) pokūnis, GF (q^{n}) ⊂ GF (q^{m}), tai m dalijasi iš n.

Tegu f_{q^{m}}(x) dalijasi iš f(x). Tada visos polinomo f(x) šaknys yra ir polinomo f_{q^{m}}(x) šaknys. Todėl GF (q^{n}) ⊂ GF (q^{m}) ir m dalijasi iš n.

Priešingai, tegu m dalijasi iš n. Tada GF (q^{n}) ⊂ GF (q^{m}) ir visos polinomo f(x) šaknys priklauso kūnui GF (q^{m}). Bet kūno GF (q^{m}) elementai – tai polinomo f_{q^{m}}(x) šaknys ir todėl polinomo f(x) šaknis α yra polinomo f_{q^{m}}(x) šaknis. Taigi f_{q^{m}}(x) dalijasi iš f(x).

△

Neredukuojamu_{‘} polinomu_{‘} virš baigtiniu_{‘} kūnu_{‘} šaknys reiškiamos paprastai.

11.3 teiginys. Tegu f(x) ∈ GF (q) [x] yra n-ojo laipsnio neredukuojamas polinomas ir α – kuri nors polinomo f(x) šaknis polinomo skaidinio kūne GF (q^{n}). Tada kūno GF (q^{n}) elementai

α, α^{q}, α^{q^{2}}, …, α^{q^{n−1}}

yra visos skirtingos polinomo f(x) šaknys ir n yra mažiausias natūralusis skaičius, kuriam teisinga lygybė α^{q^{n}} = α.

I_{‘} rodymas. Tegu f(x) = a_{0} + a_{1}x + … + a_{n}x^{n}, a_{i} ∈ GF (q), 0 ⩽ i ⩽ n, o α – polinomo f(x) šaknis polinomo skaidinio kūne GF (q^{n}):

f(α) = a_{0} + a_{1} α + … + a_{n}α^{n} = 0.

Kūno GF (q^{n}) charakteristika yra pirminis skaičius p, o q yra p laipsnis. Todėl a_{i}^{q} = a_{i} ir

f(α^{q}) = a_{0} + a_{1}α^{q} + … + a_{n}α^{qn} = a_{0}^{q} + a_{1}^{q}α^{q} + … + a_{n}^{q}α^{qn}
= a_{0}^{q} + (a_{1} α)^{q} + … + (a_{n}α^{n})^{q} = (a_{0} + a_{1}α + … + a_{n}α^{n})^{q}
= (f(α))^{q} = 0.

Taigi, jeigu α yra polinomo f(x) šaknis, tai ir α^{q} yra šio polinomo šaknis, taip pat šaknys yra ir elementai

α, α^{q}, α^{q^{2}}, …, α^{q^{n−1}}.

Visi šioje sekoje esantys elementai yra skirtingi, nes, jeigu α^{q^{i}} = α^{q^{j}}, 0 ⩽ i < j ⩽ n − 1, tai

(α^{q^{i}})^{q^{n−j}} = (α^{q^{j}})^{q^{n−j}},
α^{q^{n+i−j}} = α^{q^{n}} = α,
α^{q^{n+i−j}} − α = 0,

t.y. α būtu_{‘} polinomo f_{q^{n+i−j}}(x) = x^{q^{n+i−j}} − x šaknis ir tada polinomas f_{q^{n+i−j}}(x) dalytu_{‘}si iš f(x), ir n + i − j dalytu_{‘}si iš n. Bet tai prieštarauja nelygybėms 0 < n + i − j < n.

△

11.4 išvada. Tegu f(x) ∈ GF (q) [x] yra n-jo laipsnio neredukuojamas polinomas ir α, α^{q}, α^{q^{2}}, …, α^{q^{n−1}} – šio polinomo šaknys kūne GF (q^{n}). Tada šiu_{‘} šaknu_{‘} eilės kūno GF (q^{n}) multiplikacinėje grupėje GF (q^{n})^{∗} yra lygios:

ord_{GF (q^{n})^{∗}}(α) = ord_{GF (q^{n})^{∗}}(α^{q}) = … = ord_{GF (q^{n})^{∗}}(α^{q^{n−1}}).

I_{‘} rodymas. Grupė GF (q^{n})^{∗} yra (q^{n} − 1)-osios eilės ciklinė grupė, todėl elemento α eilė šioje grupėje yra q^{n} − 1 daliklis:

q^{n} − 1 = m · ord_{GF (q^{n})^{∗}}(α).

Tada

ord_{GF (q^{n})^{∗}}(α^{q^{i}}) = \frac{ord_{GF (q^{n})^{∗}}(α)}{DBD (q^{i}, ord_{GF (q^{n})^{∗}}(α))} = \frac{ord_{GF (q^{n})^{∗}}(α)}{DBD(q^{i}, \frac{q^{n}−1}{m})} =

= ord_{GF (q^{n})^{∗}}(α), 0 ⩽ i ⩽ n − 1,

nes q = p^{s}, p = char GF (q) ir 1 ⩽ DBD(q^{i}, \frac{q^{n}−1}{m}) ⩽ DBD(q^{i}, q^{n} − 1) = 1.

△

11.5 apibrėžimas. Neredukuojamo polinomo f(x) eile vadinamas skaičius, lygus šio polinomo kurios nors šaknies eilei jo skaidinio kūno multiplikacinėje grupėje ir žymimas ord(f(x)), arba ord(f).

Pateiksime pagrindines neredukuojamo polinomo eilės savybes, kuriu_{‘} i_{‘}rodymai remiasi mums jau žinomais teiginiais.

11.6 teiginys. Tegu f(x) yra neredukuojamas polinomas virš GF (q) ir deg (f(x)) = n. Teisingi šie teiginiai:

1. ord f(x) yra q^{n} − 1 daliklis.

2. Polinomas f(x) yra polinomo u_{ord(f(x))}(x) = x^{ord(f)} − 1 daliklis.

3. ord (f) yra m daliklis tada ir tik tada, kai f(x) yra u_{m}(x) = x^{m} − 1 daliklis.

4. ord (f) yra toks mažiausias teigiamas sveikas skaičius e, kad polinomas f(x) yra u_{e}(x) = x^{e} − 1 daliklis.

5. Tegu f(x) = x^{n}+a_{n−1}x^{n−1}+a_{n−2}x^{n−2}+…+a_{0}, a_{0} ≠ 0. Polinomo f(x) eilė ord(f(x)) yra lygi polinomo f(x) lydinčiosios matricos

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

eilei multiplikacinėje neišsigimusiu_{‘} matricu_{‘} grupėje GL(n, GF (q)).

I_{‘} rodymas. 1. Polinomo f(x) skaidinio kūnas yra GF (q^{n}) ir kiekviena polinomo f(x) šaknis yra polinomo u_{q^{n}−1}(x) = x^{q^{n}−1} − 1 šaknis. Taigi visu_{‘} polinomo f(x) šaknu_{‘} eilės yra q^{n} − 1 dalikliai.

2. Visu_{‘} polinomo f(x) šaknu_{‘} eilės lygios ord(f), t.y. visos jos yra polinomo u_{ord(f)} = x^{ord(f)} − 1 šaknys. Todėl f(x) yra u_{ord(f)}(x) daliklis.

3. Tegu f(x) yra u_{m}(x) daliklis. Tada visos polinomo f(x) šaknys yra ir u_{m}(x) šaknys ir šiu_{‘} šaknu_{‘} eilės yra m dalikliai. Todėl ord f yra m daliklis. Atvirkščiai, tegu m = m_{1} · ord(f). Tada u_{ord(f)}(x) = x^{ord(f)} − 1 yra x^{m_{1}·ord(f)} − 1 = x^{m} − 1 = u_{m}(x) daliklis ir iš šio teiginio 2 dalies gauname, kad f(x) yra u_{m}(x) daliklis.

4. Šis teiginys yra 3 dalies tiesioginė išvada.

5. Polinomas f(x) yra matricos A minimalusis polinomas, todėl A^{e} = I tada ir tik tada, kai f(x) yra polinomo u_{e}(x) = x^{e}−1 daliklis. Tada norimas rezultatas išplaukia iš polinomo f(x) eilės ir matricos A ∈ GL(n, GF (q)) eilės apibrėžimu_{‘}.

△

Neredukuojamojo polinomo eilės skaičiavimo būda_{‘} panagrinėsime kiek vėliau, o dabar apsiribosime pavyzdžiu.

11.7 pavyzdys. Pateiksime mums jau žinomu_{‘} neredukuojamu_{‘} polinomu_{‘} virš kūno GF (2) eiliu_{‘} lentele_{‘}

\begin{matrix}f(x) & deg f(x) = n & 2^{n} − 1 & ord (f) \\ x & 1 & 1 & 1 \\ x + 1 & 1 & 1 & 1 \\ x^{2} + x + 1 & 2 & 3 & 3 \\ x^{3}  + x + 1 & 3 & 7 & 7 \\ x^{3} + x^{2}  + 1 & 3 & 7 & 7 \\ x^{4}  + x + 1 & 4 & 15 & 15 \\ x^{4} + x^{3}  + 1 & 4 & 15 & 15 \\ x^{4} + x^{3} + x^{2} + x + 1 & 4 & 15 & 5 \end{matrix}

Iš šio pavyzdžio matome, kad neredukuojamo polinomo laipsnis nelemia šio polinomo eilės: polinomu_{‘} q(x) = x^{4} + x + 1 ir p(x) = x^{4} + x^{3} + 1 eilė yra lygi 15, o polinomo r(x) = x^{4} + x^{3} + x^{2} + x + 1 eilė lygi 5.

11.8 teiginys. Tegu polinomas f(x) ∈ GF (q) [x] ir deg f(x) = n ⩾ 1. Šios sa_{‘}lygos yra ekvivalenčios:

1. Polinomas f(x) yra primityviojo plėtinio GF (q^{n}) virš GF (q) elemento minimalusis polinomas.

2. f(x) yra toks unitarusis polinomas, kad ord (f(x)) = q^{n} − 1.

Polinomas f(x), tenkinantis teiginio sa_{‘}lygas, vadinamas primityviuoju polinomu.

Taigi primityvusis n-ojo laipsnio polinomas virš GF (q) yra toks neredukuojamas polinomas virš GF (q), kad jo šaknis α ∈ GF (q^{n}) yra generuojantis kūno GF (q^{n}) multiplikacinės grupės GF (q^{n})^{∗} elementas.

Dabar pateiksime neredukuojamo polinomo f(x) ∈ GF (q) eilės skaičiavimo metoda_{‘}.

Tegu polinomo f(x) laipsnis deg f(x) = n. A. Iš 11.5 apibrėžimo žinome, kad polinomo f(x) eilė e = ord (f) yra

toks mažiausias natūralusis skaičius, kad

x^{e} ≡ 1 (mod f(x)).

B. Iš 11.6 teiginio 1 dalies žinome, kad e yra q^{n} − 1 daliklis. Todėl:

1. Randame skaičiaus q^{n} − 1 kanonini_{‘} skaidini_{‘}

q^{n} − 1 = ∏_{i=1}^{s} p_{i}^{α_{i}}.

2. Iš B gauname:

p_{i}^{α_{i}} yra e daliklis ⟺ e nėra \frac{q^{n} − 1}{p_{i}} daliklis ⟺

f(x) nėra x^{\frac{q^{n}−1}{p_{i}}} − 1 daliklis ⟺

x^{\frac{q^{n}−1}{p_{i}}} ≢ 1 (mod f(x)).

3. Aišku, jeigu x^{\frac{q^{n}−1}{p_{i}}} ≡ 1 (mod f(x)), tai p_{i}^{α_{i}} nėra skaičiaus e daliklis ir todėl turėtume ieškoti tokio mažiausio skaičiaus r_{i}, 0 ⩽ r_{i} ⩽ α_{i}, kad

x^{\frac{q^{n}−1}{p{r_{i} \atop i}}} ≢ 1 (mod f(x)).

Tada p_{i}^{α_{i}−(r_{i}−1)} = p_{i}^{α_{i}−r_{i}+1} – didžiausias pirminio skaičiaus p_{i} laipsnis – skaičiaus e daliklis. Tokiu būdu kiekvienam i, 1 ⩽ i ⩽ s, surade_{‘} r_{i}, gausime

e = ∏_{i=1}^{s} p_{i}^{α_{i}−r_{i}+1}.

11.9 pavyzdžiai. 1. Polinomas f(x) = x^{6} + x^{5} + 1 yra neredukuojamas polinomas virš GF (2).

Kadangi q = 2, tai q^{6} − 1 = 63 = 3^{2} · 7.

Patikrinsime, ar 3^{2} yra ord (f) daliklis. Kadangi \frac{63}{3} = 21, tai

3^{2} yra ord (f) daliklis ⟺ x^{21} ≢ 1 (mod x^{6} + x^{5} + 1).

Pritaike_{‘} polinomu_{‘} porai x^{21} ir x^{6} + x^{5} + 1 dalybos algoritma_{‘}, gausime

x^{21} ≡ x^{5} + x^{2} + x (mod x^{6} + x^{5} + 1) ≢ 1.

Taigi 3^{2} yra ord (f) daliklis.

Patikrinsime, ar 7 yra ord (f) daliklis. Kadangi \frac{63}{7} = 9, tai

7 yra ord(f) daliklis ⟺ x^{9} ≢ 1 (mod x^{6} + x^{5} + 1).

Bet x^{9} ≡ x^{5} + x^{3} + x^{2} + x + 1 (mod x^{6} + x^{5} + 1) ≢ 1 ir todėl 7 yra ord (f) daliklis.

Taigi ord (f) = 63 ir, be to, matome, kad polinomas f(x) yra primityvusis polinomas virš GF (2).

2. Polinomas g(x) = x^{6} + x^{5} + x^{4} + x^{2} + 1 yra neredukuojamas polinomas virš GF (2).

q = 2, q^{6} − 1 = 63 = 3^{2} · 7.
3^{2} yra ord (g) daliklis ⟺ x^{21} ≢ 1 (mod x^{6} + x^{5} + x^{4} + x^{2} + 1).

Bet x^{21} ≡ 1(mod x^{6} + x^{5} + x^{4} + x^{2} + 1) ir todėl 9 = 3^{2} nėra ord (g) daliklis.

Patikrinsime, ar 3 yra ord (g) daliklis. Kadangi \frac{63}{3^{2}} = 7, tai

3 yra ord (g) daliklis ⟺ x^{7} ≢ 1 (mod x^{6} + x^{5} + x^{4} + x^{2} + 1).

Padalije_{‘} gausime x^{7} ≡ x^{4} +x^{3} +x^{2} +x+1 (mod x^{6} +x^{5} +x^{4} +x^{2} +1) ≢ 1, ir todėl 3 yra ord (g) daliklis.

Pagaliau,

7 yra ord (g) daliklis ⟺ x^{9} ≢ 1 (mod x^{6} + x^{5} + x^{4} + x^{2} + 1).

Padalije_{‘} gausime x^{9} ≡ x^{3} + 1 (mod x^{6} + x^{5} + x^{4} + x^{2} + 1) ≢ 1 ir todėl 7 yra ord (g) daliklis.

Taigi ord (g) = 3 · 7 = 21.