12. BAIGTINIAI KŪNAI

Ankstesniuose skyreliuose jau nagrinėjome baigtiniu_{‘} kūnu_{‘} pavyzdžius: likiniu_{‘} klasiu_{‘} pirminio skaičiaus p moduliu kūna_{‘}, ℤ/(p) = GF (p) – svarbiausias iš ju_{‘}. Dabar apibendrinsime mūsu_{‘} žinias apie baigtiniu_{‘} kūnu_{‘} struktūra_{‘}, aptarsime polinomu_{‘} su koeficientais iš šiu_{‘} kūnu_{‘} savybes. Ypač mus domins baigtinio kūno elementu_{‘} minimaliu_{‘}ju_{‘} polinomu_{‘} paieška, taip pat polinomu_{‘} virš baigtiniu_{‘} kūnu_{‘} faktorizacijos klausimai.

Pradžioje pastebėsime, kad bet kurio baigtinio kūno K charakteristika yra pirminis skaičius p, ir todėl i_{‘} baigtini_{‘} kūna_{‘} K galima žiūrėti kaip i_{‘} pirminio kūno GF (p) baigtini_{‘} plėtini_{‘}.

9.1 teiginys. Tegu baigtinis kūnas K yra baigtinio kūno F plėtinys ir [K : F] = d. Tada |K| = |F |^{d}.

I_{‘} rodymas. Tegu {a_{1}, …, a_{d}} yra vektorinės erdvės K virš F bazė. Tada

\begin{aligned}K & = \{α_{1}a_{1} + … + α_{d}a_{d} | α_{1}, …, α_{d} ∈ F \} ir \\ |K| & = |F |^{d}. \end{aligned}

△

9.2 išvada. Tegu K baigtinis kūnas, kurio char K = p. Tada kūne K yra p^{n} elementu_{‘}; čia n = [K : GF (p)].

I_{‘} baigtinio kūno elementus galima žiūrėti ir kaip i_{‘} polinomo šaknis.

9.3 teiginys. Tegu |(K, +, ·)| = q. Tada:

1) visi kūno K elementai yra polinomo f_{q}(x) = x^{q} − x šaknys;

2) kūnas K yra polinomo f_{q}(x) skaidinio kūnas.

I_{‘} rodymas. 1) Aišku, kad f(0) = 0^{q} − 0 = 0. Be to, (K^{∗}, ·) = (K − {0}, ·) – yra multiplikacinė grupė, kurios eilė lygi q − 1, ir pagal 5.19 Lagranžo teorema_{‘}, kai a ∈ K^{∗}, tai a^{q−1} = 1 ir a^{q} = a.

2) Polinomas f_{q}(x) gali turėti daugiausiai q šaknu_{‘} kūne K. Bet mes jas visas jau žinome – tai kūno K elementai:

f_{q}(x) = (x − a_{1})(x − a_{2}) … (x − a_{q});

čia a_{1}, a_{2}, …, a_{q} – visi kūno K elementai. Taigi K yra polinomo f_{q}(x) skaidinio kūnas.

△

9.4 teiginys. 1. Visiems pirminiams skaičiams p ir visiems natūraliesiems skaičiams n egzistuoja kūnas, turintis p^{n} elementu_{‘}.

2. Visi baigtiniai kūnai, turintys q = p^{n} elementu_{‘}, yra izomorfiški polinomo f_{q}(x) = x^{q} − x skaidinio kūnui.

I_{‘} rodymas. Tegu K yra polinomo f_{q}(x) = x^{q} − x ∈ GF (p)[x] skaidinio kūnas, o aibė A ⊆ K – polinomo f_{q}(x) šaknu_{‘} aibė. Aibėje A yra q elementu_{‘}, nes polinomas f_{q}(x) neturi kartotiniu_{‘} šaknu_{‘}: f′_{q}(x) = qx^{q−1} − 1 = −1 ≠ 0 ir (f_{q}(x), f′_{q}(x)) = 1. Aibė A yra kūnas, nes:

a) 0, 1 ∈ A : 0^{q} = 0, 1^{q} = 1;

b) kai b ∈ A, b ≠ 0, tai ir −b ∈ A, nes (−b)^{q} = −b, ir b^{−1} ∈ A, nes (b^{−1})^{q} = (b^{q})^{−1} = b^{−1};

c) kai a, b ∈ A, b ≠ 0, tai

\begin{matrix}a ± b ∈ A : (a ± b)^{q} = a^{q} ± b^{q} = a ± b; \\ a · b^{−1} ∈ A : (a · b^{−1})^{q} = a^{q} · (b^{q})^{−1} = a · b^{−1}. \end{matrix}

Polinomas f_{q}(x) taip pat skaidosi tiesiniu_{‘} daugikliu_{‘} sandauga virš kūno A, t. y. A – polinomo f_{q}(x) skaidinio kūnas ir A = K. Taigi |K| = q.

△

Visi baigtiniai kūnai, turintys q = p^{n} ( p – pirminis) elementu_{‘}, izomorfiški vieni kitiems (visi jie izomorfiški polinomo f_{q}(x) = x^{q} − x skaidinio kūnui) ir todėl galima kalbėti apie kūno iš q elementu_{‘} vienatinuma_{‘}. Visus šiuos kūnus žymėsime vienodai – GF (q). Tiesa, lieka atviras kūno elementu_{‘} reiškimo klausimas. Bet apie tai vėliau. Nagrinėjant kūno struktūra_{‘} svarbu išsiaiškinti, kokiu_{‘} kūnu_{‘} plėtinys yra nagrinėjamas kūnas. Baigtiniams kūnams i_{‘} ši_{‘} klausima_{‘} galima atsakyti tiksliai.

9.5 teiginys. Tegu K yra baigtinis kūnas, turintis q = p^{n} (p – pirminis) elementu_{‘}.

1. Kai F yra kūno K pokūnis, tai |F | = p^{d}; čia d yra n daliklis.

2. Kiekvienam skaičiaus n dalikliui d egzistuoja vienintelis kūno K pokūnis F, turintis p^{d} elementu_{‘}.

I_{‘} rodymas. 1. Aišku, kad K ⊇ F ⊇ GF (p) ir |F | = p^{d}; čia d = [F : GF (p)]. Bet n = [K : GF (p)] = [K : F][F : GF (p)] = [K : F] · d, todėl d yra n daliklis.

2. Tegu d yra n daliklis. Tada p^{d} − 1 yra p^{n} − 1 daliklis ir x^{p^{d}−1} − 1 yra x^{p^{n}−1} − 1 daliklis, t. y. f_{p^{n}}(x) dalijasi iš f_{p^{d}}(x) ir kiekviena polinomo f_{p^{d}}(x) šaknis yra ir polinomo f_{p^{n}}(x) šaknis. Kūnas K yra polinomo f_{p^{n}}(x) skaidinio kūnas ir todėl jame bus polinomo f_{p^{d}}(x) skaidymo kūnas F, kuriame p^{d} elementu_{‘}. Bet kūno F elementai – tai polinomo f_{p^{d}}(x) šaknys, o ju_{‘} yra p^{d}, t.y. kiek elementu_{‘} kūne F. Taigi dvieju_{‘} skirtingu_{‘} polinomo f_{p^{d}}(x) skaidinio kūnu_{‘} kūne K negali būti.

△

9.6 pavyzdys. Kūno GF (2^{24}) pokūniu_{‘} diagrama atitinka skaičiaus n = 24 dalikliu_{‘} diagrama_{‘}:

1 2 4 8^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} 3 6 12 24^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} GF(2^{24}) GF(2^{12})  GF(2^{8}) GF(2^{6})  GF(2^{4}) GF(2^{3})  GF(2^{2}) GF(2^{1})^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}

Svarbi baigtiniu_{‘} kūnu_{‘} savybė yra ir ta, kad baigtinio kūno (K, +, ·) multiplikacinė grupė K^{∗} = (K − {0}, ·) yra ciklinė. Šia_{‘} grupe_{‘} generuojantys elementai vadinami primityviaisiais kūno K elementais (palyginkite su jau nagrinėtos grupės U_{n} generuojančiais elementais, kurie taip pat vadinami primityviaisiais).

Pastebėsime, kad multiplikacinė kūno GF (p) grupė GF (p)^{∗} yra lygi U_{p} (žr. 6.7 pastaba_{‘} ). Tačiau net ir šiuo atveju nėra formulės primityviajam elementui rasti. Tiesa, yra žinoma, jeigu pirminis skaičius p = 4q + 1, čia q – taip pat pirminis skaičius, tai 2 yra primityvusis elementas grupėje U_{p} = GF (p)^{∗}, t. y. 2 – primityvusis kūno GF (4q + 1), q – pirminis, elementas. Tokiu_{‘} kūnu_{‘} pavyzdžiai yra GF (5), GF (13), GF (17), GF (29) ir t.t.

6.19 algoritmas, pagal kuri_{‘} randamos primityviosios šaknys mod p, visiškai tinka ir kūno GF (q) primityviesiems elementams ieškoti. Pačiame algoritme reikėtu_{‘} tik pirmini_{‘} skaičiu_{‘} p pakeisti skaičiumi q. Pabandykime i_{‘}sitikinti tuo, kad pagal algoritma_{‘} galima rasti elementa_{‘} a ∈ GF (q)^{∗}, kurio eilė ord_{GF (q)^{∗}}(a) = q − 1.

1. Tegu r = q −1 = p_{1}^{n_{1}}p_{2}^{n_{2}} … p_{m}^{n_{m}} yra kanoninis skaičiaus r skaidinys.

2. Tegu a_{i} ∈ GF (q)^{∗} toks elementas, kad ai^{\frac{r}{p_{i}}} ≠ 1, 1 ⩽ i ⩽ m. Toks elementas su visais i atsiras, nes polinomas x^{\frac{r}{p_{i}}} − 1 turi kūne ne daugiau kaip \frac{r}{p_{i}} < r šaknu_{‘}.

3. Elemento b_{i} = ai^{\frac{r}{p{n_{i} \atop i}}} eilė lygi p_{i}^{n_{i}}, nes

\begin{matrix}b_{i}^{p_{i}^{n_{i}}} = (a^{\frac{r}{p{n_{i} \atop i}}} )^{p_{i}^{n_{i}}} = a^{r} = 1, bet \\ b_{i}^{p_{i}^{n_{i}−1}} = (a^{\frac{r}{p{n_{i} \atop i}}} )^{p_{i}^{n_{i}−1}} = a^{\frac{r}{p_{i}}} ≠ 1. \end{matrix}

4. Elementas a = b_{1}b_{2} … b_{m} yra primityvusis kūno GF (q) elementas. Tai, kad a^{r} = a^{q−1} = 1, žinoma. Bet

a^{\frac{r}{p_{i}}} = b1^{\frac{r}{p_{i}}} … bi−1^{\frac{r}{p_{i}}}bi^{\frac{r}{p_{i}}} bi+1^{\frac{r}{p_{i}}} … bm^{\frac{r}{p_{i}}} = b^{\frac{r}{p_{i}}} ≠ 1, 1 ⩽ i ⩽ m.

Primityviu_{‘}ju_{‘} elementu_{‘} kiekis baigtiniame kūne GF (q) yra φ(q − 1); čia φ – Oilerio funkcija.

I_{‘}domi primityviojo elemento egzistavimo baigtiniame kūne išvada yra tokia:

9.7 teiginys. Tegu GF (q) yra baigtinis kūnas. Su visais natūraliaisiais n egzistuoja neredukuojamas n-ojo laipsnio polinomas virš GF (q).

I_{‘} rodymas. Kūnas GF (q^{n}) yra toks kūno GF (q) plėtinys, kad [GF (q^{n}) : GF (q)] = n. Jeigu a yra primityvusis kūno GF (q^{n}) elementas, tai (GF (q))(a) = GF (q^{n}) ir minimalusis elemento a polinomas m(x) bus tas ieškomasis neredukuojamas n-ojo laipsnio polinomas virš GF (q).

△