17. CIKLOTOMINIAI POLINOMAI

Ieškodami polinomo u_{n}(x) = x^{n} − 1 ∈ GF (q)[x] kanoninio skaidinio, naudojomės šio polinomo skaidinio kūnu GF (q^{s}). Norint faktorizuoti ši_{‘} polinoma_{‘} be kūno GF (q^{s}), svarbūs yra polinomai, kuriu_{‘} šaknys – visos primityviosios n-ojo laipsnio vieneto šaknys.

12.8 apibrėžimas. Tegu GF (q) yra baigtinis kūnas, o k – toks natūralusis skaičius, kad DBD(k, q) = 1. Jeigu ω – primityvioji k-ojo laipsnio vieneto šaknis, tai polinomas

Q_{k}(x) = ∏_{{s=1 \atop DBD(s,k)=1}}^{k}(x − ω^{s})

vadinamas k-ciklotominiu polinomu virš kūno GF (q).

Aišku, kad k-ciklotominio polinomo Q_{k}(x) šaknys yra visos primityviosios k-ojo laipsnio vieneto šaknys. Šio polinomo laipsnis yra lygus φ (k); čia φ – Oilerio funkcija.

12.9 teiginys. Tegu GF (q) yra baigtinis kūnas, kurio charakteristika yra p, t.y. q = p^{r}, o n– toks natūralusis skaičius, kad DBD(n, q) = 1. Tada:

1.

x^{n} − 1 = ∏_{k|n} Q_{k}(x).

2. k-ciklotominio polinomo Q_{k}(x) koeficientai yra kūno GF (p) elementai, t.y. Q_{k}(x) ∈ GF (p)[x].

3. Jeigu skaičiaus q eilė mod k yra s, s = ord_{k}(q), tai k-ciklotominio polinomo kanoniniame skaidinyje yra \frac{φ (k)}{s} skirtingu_{‘} vieno ir to paties s laipsnio neredukuojamu_{‘} polinomu_{‘} virš GF (q).

4. Jeigu μ – Miobiuso funkcija, tai

Q_{k}(x) = ∏_{d|k}(x^{d} − 1)^{μ( \frac{k}{d})} = ∏_{d|k}(x^{\frac{k}{d}} − 1)^{μ(d)}.

I_{‘} rodymas. 1. Jeigu ω yra primityvioji n-ojo laipsnio vieneto šaknis, tai visos n-ojo laipsnio vieneto šaknys yra ω laipsniai ω^{i}, 1 ⩽ i ⩽ n. Elementas ω^{i} taip pat yra primityvioji \frac{n}{DBD (n,i)} = k-laipsnio vieneto šaknis. Pastebėsime, kad k yra elemento ω^{i} eilė ciklinėje grupėje E_{n}. Todėl tokiu_{‘} skirtingu_{‘} n-ojo laipsnio vieneto šaknu_{‘}, kurios taip pat būtu_{‘} ir k-ojo laipsnio primityviosios vieneto šaknys, yra φ (k) (žr. 5.43 teiginio 4a) dali_{‘}). Polinomo u_{n}(k) skaidinyje

x^{n} − 1 = ∏_{i=1}^{n}(x − ω^{i})

sugrupave_{‘} tuos daugiklius (x − ω^{i}), kuriuose ω^{i} yra primityvioji k-ojo laipsnio vieneto šaknis (k – bet kuris teigiamas skaičiaus n daliklis), ir gausime teiginyje esančia_{‘} išraiška_{‘}.

2. Prisiminkime, kad polinomo u_{n}(x) kanoninis skaidinys virš kūno GF (p) yra

x^{n} − 1 = ∏_{i} m_{i}(x);

čia m_{i}(x) yra skirtingi minimalieji n-ojo laipsnio vieneto šaknu_{‘} polinomai. Tada Q_{k}(x) yra tokiu_{‘} minimaliu_{‘}ju_{‘} polinomu_{‘} m_{i}(x) sandauga, kad k = ord m_{i}(x) ir todėl Q_{k}(x) ∈ GF (p)[x].

3. Jeigu ω yra bet kuri primityvioji k-ojo laipsnio vieneto šaknis virš kūno GF (q), tai

ω ∈ GF (q^{i}) ⟺ ω^{q^{i}} = ω ⟺ q^{i} ≡ 1 (mod k)

ir s = ord_{k}(q) yra toks mažiausias natūralusis skaičius, kad

ω ∈ GF (q^{s}), bet ω ∉ GF (q^{j}), j < s.

Tada minimaliojo elemento ω polinomo laipsnis yra lygus s ir todėl visu_{‘} skirtingu_{‘} minimaliu_{‘}ju_{‘} polinomu_{‘}, kuriu_{‘} šaknys yra primityviosios k-ojo laipsnio vieneto šaknys, laipsniai yra lygūs s. Bet iš viso yra φ (k) skirtingu_{‘} primityviu_{‘}ju_{‘} k-ojo laipsnio vieneto šaknu_{‘}, todėl skirtingu_{‘} neredukuojamu_{‘} polinomu_{‘} virš GF (q), kuriu_{‘} laipsnis yra s, yra \frac{φ (k)}{s}. Šiu_{‘} polinomu_{‘} sandauga ir yra k-ciklotominio polinomo kanoninis skaidinys.

4. Tegu h(k) = Q_{k}(x) ir H(k) = x^{k} − 1 su visais k ∈ ℕ yra funkcijos, kuriu_{‘} reikšmės yra multiplikacinėje nenuliniu_{‘} racionaliu_{‘}ju_{‘} funkciju_{‘} virš kūno GF (q) grupėje. Iš šio teiginio 1-osios dalies x^{k} − 1 = ∏_{d|k} Q_{d}(x), t.y.

H(k) = ∏_{d|k} h(d). Paskutinei lygybei pritaike_{‘} Miobiuso apgre_{‘}žimo formulės

multiplikatyvu_{‘}ji_{‘} varianta_{‘} (žr. 11.16 teiginio 3.2 dali_{‘}), gausime norima_{‘} ciklotominio polinomo Q_{k}(x) išraiška_{‘}.

12.10 pavyzdžiai. 1. Q_{1}(x) = x − 1 virš bet kokio kūno K.

2. Tegu GF (q) yra baigtinis kūnas, o r – pirminis skaičius, tarpusavyje pirminis skaičiui q. Tada:

a) x^{r} − 1 = Q_{1}(x) Q_{r}(x) ir todėl

Q_{r}(x) = \frac{x^{r} − 1}{Q_{1}(x)} = \frac{x^{r} − 1}{x − 1} = x^{r−1} + x^{r−2} + … + x^{2} + x + 1;

b) x^{r^{k}} − 1 = Q_{1}(x) Q_{r}(x) Q_{r^{2}}(x) … Q_{r^{k}}(x) ir todėl

\begin{aligned}Q_{r^{k}}(x) & = \frac{x^{r^{k}} − 1}{Q_{1}(x) Q_{r}(x) Q_{r^{2}}(x) … Q_{r^{k−1}}(x)} \\ & = \frac{x^{r^{k}} − 1}{x^{r^{k−1}} − 1} = x^{(r−1)r^{k−1}} + x^{(r−2)r^{k−1}} + … + x^{r^{k−1}} + 1. \end{aligned}

3. Virš kūno GF (2) teisinga

x^{15} − 1 = Q_{1}(x) Q_{3}(x) Q_{5}(x) Q_{15}(x).

Žinome, kad:

Q_{1}(x) = x − 1 = x + 1,

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

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

Q_{15}(x) = ∏_{d|15} (x^{\frac{15}{d}} − 1)^{μ(d)}

= (x^{15} − 1)^{μ(1)}(x^{5} − 1)^{μ(3)}(x^{3} − 1)^{μ(5)}(x − 1)^{μ(15)}

= (x^{15} − 1)(x^{5} − 1)^{−1}(x^{3} − 1)^{−1}(x − 1) = \frac{(x^{15} − 1)(x − 1)}{(x^{5} − 1)(x^{3} − 1)}

= x^{8} + x^{7} + x^{5} + x^{4} + x^{3} + x + 1.

Taigi turime polinomo u_{n}(x) skaidini_{‘} ciklotominiu_{‘} polinomu_{‘} sandauga:

\begin{aligned}x^{15} − 1 & = (x + 1)(x^{2} + x + 1)(x^{4} + x^{3} + x^{2} + x + 1) \\ & · (x^{8} + x^{7} + x^{5} + x^{4} + x^{3} + x + 1). \end{aligned}

Palygine_{‘} ši_{‘} polinomo u_{n}(x) skaidini_{‘} su kanoniniu u_{n}(x) skaidiniu

\begin{aligned}x^{15} − 1 & = (x + 1)(x^{2} + x + 1)(x^{4} + x^{3} + x^{2} + x + 1) \\ & · (x^{4} + x^{3} + 1)(x^{4} + x + 1), \end{aligned}

matome, kad polinomo Q_{15}(x) kanoninis skaidinys yra

Q_{15}(x) = (x^{4} + x^{3} + 1)(x^{4} + x + 1);

čia polinomai x^{4} + x^{3} + 1 ir x^{4} + x + 1 yra 15-ojo laipsnio primityviu_{‘}ju_{‘} vieneto šaknu_{‘} minimalieji polinomai ir todėl šiu_{‘} polinomu_{‘} eilė yra lygi 15. Apibrėžtas 12.9 teiginio 3 dalyje natūralusis skaičius s = ord_{k}(q) šiuo atveju yra lygus s = ord_{15}(2) = 4 ir todėl Q_{15}(x) yra \frac{φ (15)}{4} = 2 neredukuojamu_{‘} polinomu_{‘} virš GF (2) sandauga.

12.11 pastaba. Visos ciklotominio polinomo Q_{q^{n}−1}(x) ∈ GF (q)[x] šaknys yra (q^{n}−1) laipsnio primityviosios vieneto šaknys virš kūno GF (q), ir todėl šio polinomo kanoniniame skaidinyje yra visi primityvieji n-ojo laipsnio polinomai virš GF (q). Taigi dar karta_{‘} i_{‘}sitikiname, kad polinomai x^{4} + x^{3} + 1 ir x^{4} + x + 1 yra visi primityvieji 4-ojo laipsnio polinomai virš kūno GF (2).

Nagrinėjant neredukuojamus polinomus virš kūno GF (q) , naudinga žinoti, kada jie išlieka neredukuojamais polinomais virš minėto kūno plėtinio

GF (q^{k}). Dabar mes galime atsakyti i_{‘} ši_{‘} klausima_{‘}.

12.12 teiginys. Tegu f yra n-ojo laipsnio neredukuojamas polinomas virš kūno GF (q). Tada:

1. Jeigu k ∈ ℕ, tai polinomu_{‘} žiede GF (q^{k})[x] polinomo f kanoniniame skaidinyje yra d = DBD (k, n) neredukuojamu_{‘} to paties \frac{n}{d} laipsnio polinomu_{‘}.

2. Polinomas f yra neredukuojamas virš GF (q^{k}) tada ir tik tada, kai DBD (k, n) = 1.

I_{‘} rodymas. 1. Tegu polinomo f eilė lygi e, ord(f) = e (žr. 11.5 apibrėžima_{‘}). Jeigu polinomas g yra bet kuris neredukuojamas polinomo f daliklis, tai ord(g) = ord(f) = e, nes visos polinomo g šaknys yra polinomo f šaknys, o polinomo f eilė yra lygi kurios nors (nesvarbu kurios) savo šaknies eilei polinomo f skaidinio kūno multiplikacinėje grupėje. Žinome, kad šie teiginiai yra ekvivalentūs (žr. 11.6 teigini_{‘}):

1) ord f = e;

2) visos polinomo f šaknys yra primityviosios e-ojo laipsnio vieneto šaknys;

3) polinomas f yra ciklotominio polinomo Q_{e}(x) daliklis;

4) neredukuojamo polinomo f laipsnis n yra toks mažiausias natūralusis skaičius, kuriam q^{n} ≡ 1 (mod e), o neredukuojamo polinomo g laipsnis m yra toks mažiausias natūralusis skaičius, kuriam (q^{k})^{m} ≡ 1 (mod e).

Bet elemento q^{k} eilė ciklinėje grupėje G

G = {q (mod e), q^{2}( mod e), …, q^{n−1} (mod e), q^{n} (mod e) = 1} ≈ ℤ_{n},

yra lygi

ord_{G}q^{k} = \frac{n}{DBD(k, n)} = \frac{n}{d},

todėl polinomo g laipsnis yra lygus \frac{n}{d}. Dabar aišku, kodėl polinomo f kanoniniame skaidinyje yra d neredukuojamu_{‘} polinomu_{‘}.

2. Jeigu DBD(k, n) = 1, tai iš ka_{‘} tik i_{‘}rodyto teiginio žinome, kad polinomo f kanoniniame skaidinyje virš kūno GF (q^{k}) yra vienas neredukuojamas polinomas, t.y. tas pats polinomas f.

△

12.13 pavyzdys. Polinomas f(x) = x^{4} + x^{3} + 1 yra neredukuojamas polinomas virš kūno GF (2). Neredukuojamu šis polinomas yra ir virš kūnu_{‘} GF (2^{2n−1}), n ∈ ℕ, (pavyzdžiui, GF (8), GF (32)), o štai virš kūnu_{‘} GF (2^{2n}), n ∈ ℕ, polinomo f(x) kanoniniame skaidinyje yra arba du 2-ojo laipsnio neredukuojami polinomai (kai n = 2k+1, k ∈ ℕ, nes DBD(4, 4k+ 2) = 2), arba keturi 1-ojo laispnio neredukuojami polinomai (kai n = 2k, k ∈ ℕ, nes DBD(4, 4k) = 4).

Polinomo f(x) = x^{4} + x^{3} + 1 kanoniniame skaidinyje virš kūno GF (4) yra du 2-ojo laipsnio neredukuojami polinomai: f(x) = f_{1}(x) f_{2}(x). Tegu a yra polinomo f_{1}(x) viena iš šaknu_{‘}. Tada jungtinis virš kūno GF (4) šiam elementui elementas a^{4} – irgi polinomo f_{1}(x) šaknis. Elementas a yra primityvusis polinomo f(x) skaidinio kūno GF (16) elementas (plg. su 10.2 pavyzdžiu). Todėl

\begin{aligned}f_{1}(x) & = (x − a)(x − a^{4}) = x^{2} − x(a + a^{4}) + a^{5} \\ & = x^{2} + x(a^{3} + a + 1) + a^{5} = x^{2} + xa^{5} + a^{5}. \end{aligned}

Padalije_{‘} polinoma_{‘} f(x) iš f_{1}(x), gausime polinoma_{‘} f_{2}(x):

f_{2}(x) = x^{2} + x · a^{10} + a^{10}.

Elementas b = a^{5} yra primityvioji 3-ojo laipsnio vieneto šaknis virš kūno GF (2), todėl

f(x) = (x^{2} + bx + b)(x^{2} + xb^{2} + b^{2});

čia b – primityvioji 3-ojo laipsnio vieneto šaknis virš GF (2).