18. POLINOMU_{‘} FAKTORIZACIJA VIRŠ BAIGTINIU_{‘} KŪNU_{‘}

Polinomo f(x) ∈ GF (q)[x] faktorizacija atliekama keliais žingsniais: I (bekvadratė faktorizacija). Ieškoma tokiu_{‘} polinomu_{‘} f_{1}, f_{2}, …, f_{k} ∈

GF (q)[x], kad:

a) f = f_{1}^{1}f_{2}^{2} … f_{k}^{k},

b) polinomai f_{i} būtu_{‘} tarpusavyje pirminiai ir bekvadračiai, t.y. savo kanoniniuose skaidiniuose virš kūno GF (q) neturėtu_{‘} neredukuojamu_{‘} polinomu_{‘} laipsniu_{‘}.

II. Faktorizuojami polinomai f_{i}, 1 ⩽ i ⩽ k . III. Gautame polinomo f skaidinyje sutraukiami panašūs nariai ir

gaunamas polinomo f kanoninis skaidinys.

Tegu kūno GF (q) charakteristika yra p.

Aptarsime šiuos polinomo f faktorizacijos žingsnius.

I. Tegu f = ∏_{i=1}^{k} f_{i}^{i} (čia f_{i} yra bekvadračiai) - tarpusavyje pirminiai

polinomai. Tada polinomo f išvestinė yra

f′ = ∑_{i=1}^{k} (i f′_{i} f_{i}^{i−1} ∏_{{j≠i \atop 1⩽j⩽k}} f_{j}^{j}) = ∑_{i=1}^{k} c_{i}(x).

Tegu d(x) = DBD (f, f′). Pastebėsime, jeigu neredukuojamas polinomas r(x) yra polinomo f(x) daliklis, tai r(x) yra ir f_{i_{0}}(x) daliklis kuriam nors i_{0} = i_{0}(r), 1 ⩽ i_{0} ⩽ k. Todėl neredukuojamo polinomo r(x) laipsnio rodiklis e = e_{r}(d) kanoniniame polinomo d(x) skaidinyje apibrėžiamas taip:

a) jeigu i ≠ i_{0}, tai e_{r}(d) i-ajame polinomo f′ dėmenyje c_{i}(x) yra didesnis arba lygus i_{0};

b) jeigu i = i_{0}, tai e_{r}(d) = i_{0} − 1, kai p nėra i_{0} daliklis, ir e_{r}(d) = i_{0}, kai p yra i_{0} daliklis.

Taigi

e_{r}(d) = \{ \begin{matrix}i_{0} − 1, & kai p nėra i_{0} daliklis , \\ i_{0}, & kai p yra i_{0} daliklis. \end{matrix}

d(x) = DBD (f, f′) = ∏_{i=1 p nėra i daliklis}^{k} f_{i}^{i−1} ∏_{i=1 p yra i daliklis}^{k} f_{i}^{i}.

Apibrėžkime rekurenčiuosius sa_{‘}ryšius. Tegu d_{1}(x) = d(x), o

g_{1}(x) = \frac{f(x)}{d(x)} = ∏_{i=1 p nėra i daliklis}^{k} f_{i}(x).

Kai l ⩾ 2, tai

g_{l}(x) = \{ \begin{matrix}DBD (d_{l−1}, g_{l−1}), & kai p nėra l daliklis, \\ g_{l−1}(x), & kai p yra l daliklis, \end{matrix}

d_{l}(x) = \frac{d_{l−1}(x)}{g_{l}(x)}, kai p nėra l daliklis.

Taigi

g_{l}(x) = ∏_{i>l−1 p nėra i daliklis} f_{i}(x)

ir

d_{l}(x) = ∏_{i>l p nėra i daliklis} f_{i}^{i−l} ∏_{i=1 p yra i daliklis}^{k} f_{i}^{i}.

Iš čia

f_{l}(x) = \frac{g_{l}(x)}{g_{l+1}(x)}, kai p nėra l daliklis ir

g_{l}(x) nėra lygus konstantai. Jeigu g_{l}(x) yra kūno GF (q) elementas, tai

d_{l}(x) = ∏_{i=1 p yra i daliklis}^{k} f_{i}^{i} = (h(x))^{p} = h(x^{p}).

Norint te_{‘}sti bekvadrate_{‘} faktorizacija_{‘}, polinomui h(x) reikia taikyti anksčiau nurodyta_{‘} procedūra_{‘}.

Šiais samprotavimais remiasi algoritmas.

13.1 algoritmas. Žinoma: polinomas f(x) ∈ GF (q)[x], q = p^{s}, p – pirminis.

Rezultatas: randami nelygūs konstantai bekvadračiai tarpusavyje pirminiai polinomai ir ju_{‘} laipsniu_{‘} rodikliai kanoniniame polinomo f(x) skaidinyje (1, f_{1}) = f_{1}, (2, f_{2}) = f_{2}, …, (k, f_{k}) = f_{k}; f = f_{1}^{1}f_{2}^{2} … f_{k}^{k}.

1. Priskiriame e := 1, f := f(x).

2. Jeigu f yra konstanta, tai išvedame (e, f) ir skaičiavimai baigiami. Jeigu f nėra konstanta, tai priskiriame k := 0, d := DBD (f, f′), g := \frac{f}{d}.

3. Jeigu g nėra konstanta, tai pereiname prie 4. Jeigu g yra konstanta, tai turėtu_{‘} būti

d = ∑_{p | j} t_{j}x^{j} = ∑_{p | j} t_{j}x^{j/p} = ( ∑_{q | j} t_{j}x^{j/p})^{p},

todėl priskiriame

e := pe, f := ∑_{p | j} t_{j}x^{j/p}

ir pereiname prie 2.

4. Priskiriame k := k + 1. Jeigu p nėra k daliklis, tai pereiname prie 5.

Jeigu p yra k daliklis, tai priskiriame d := \frac{d}{g}, k := k+1 ir pereiname prie 5.

5. Skaičiuojame ir priskiriame d_{ek} := DBD (d, g), f_{ek}(x) := \frac{g}{d_{ek}} , g := d_{ek}, d := \frac{d}{g}. Jeigu f_{ek} yra konstanta, tai pereiname prie 3. Jeigu f_{ek} nėra konstanta, tai išvedame (ek, f_{ek}) ir pereiname prie 3.

△

13.2 pavyzdys. f(x) = x^{10} + x^{8} + x^{6} + x^{4} + x^{2} + 1 ∈ GF (3)[x].

e = 1, k = 0. f′(x) = x^{9} + 2x^{7} + x^{3} + 2x,

d(x) = DBD(f(x), f′(x)) = x^{8} + 2x^{6} + x^{2} + 2,

g_{11}(x) = \frac{f(x)}{d(x)} = x^{2} + 2.

k = 1. d_{1}(x) = DBD(d(x), g_{11}(x)) = x^{2} + 2,

f_{1}(x) = \frac{g_{11}(x)}{d_{1}(x)} = 1,

g_{12}(x) = d_{1}(x) = x^{2} + 2,

d(x) := \frac{d(x)}{g_{12}(x)} = x^{6} + 1.

k = 2. d_{2}(x) = DBD(d(x), g_{12}(x)) = 1,

f_{2}(x) = \frac{g_{12}(x)}{d_{2}(x)} = x^{2} + 2,

g_{13}(x) = d_{2}(x) = 1,

d(x) := \frac{d(x)}{g_{13}(x)} = x^{6} + 1 = (x^{2} + 1)^{3},

g_{13}(x) − konstanta, todėl belieka suskaidyti polinoma_{‘} x^{2} + 1. Šiam polinomui vėl taikome algoritma_{‘}.

e = 3 · 1 = 3, k = 0. f(x) = x^{2} + 1,

f′(x) = 2x, d(x) = DBD(x^{2} + 1, 2x) = 1,

g_{31}(x) = \frac{f(x)}{d(x)} = x^{2} + 1.

k = 1. d_{3}(x) = DBD(d(x), g_{31}(x)) = 1,

f_{3}(x) = \frac{g_{31}(x)}{d_{3}(x)} = x^{2} + 1.

Skaičiavimai baigiami. Gavome f(x) = x^{10} + x^{8} + x^{6} + x^{4} + x^{2} + 1 = (x^{2} + 2)^{2}(x^{2} + 1)^{3}.

Polinomas x^{2} + 2 yra redukuojamas (1-as yra jo šaknis), todėl nesunkiai randame, kad x^{2} + 2 = (x + 1)(x + 2). Polinomas x^{2} + 1 neredukuojamas virš GF (3), todėl

f(x) = (x + 1)^{2}(x + 2)^{2}(x^{2} + 1)^{3}.

II. Bekvadračio polinomo faktorizacija remiasi šiais teiginiais:

13.3 teiginys (kinu_{‘} teorema liekanoms, polinominis variantas).

Tegu f_{1}(x), f_{2}(x), …, f_{n}(x) yra poromis tarpusavyje pirminiai polinomai virš kūno GF (q), o c_{1}(x), c_{2}(x), …, c_{n}(x) – bet kurie polinomai virš kūno GF (q). Tada lyginiu_{‘} sistema

f(x) ≡ c_{1}(x) (mod f_{1}(x)),
f(x) ≡ c_{2}(x) (mod f_{2}(x)),
. . . . . . . . . . . . . . . . . . . . . . . . .
f(x) ≡ c_{n}(x) (mod f_{n}(x))

turi vieninteli_{‘} sprendini_{‘} f(x) moduliu f_{1}(x)f_{2}(x) … f_{n}(x).

I_{‘} rodymas. Vienatinumas. Tegu f(x) ir g(x) yra teiginyje nurodytos lyginiu_{‘} sistemos sprendiniai. Tada

f(x) ≡ g(x) (mod f_{i}(x)), 1 ⩽ i ⩽ n,

t.y.

f(x) − g(x) dalijasi iš f_{i}(x), 1 ⩽ i ⩽ n.

Bet f_{i}(x), 1 ⩽ i ⩽ n, yra poromis tarpusavyje pirminiai, todėl f(x) − g(x) dalijasi iš f_{1}(x)f_{2}(x) … f_{n}(x) ir

f(x) ≡ g(x) (mod f_{1}(x)f_{2}(x) … f_{n}(x)).

Egzistavimas. Pažymėkime \overline{f}_{i}(x) = \frac{f_{1}(x)f_{2}(x)...f_{n}(x)}{f_{i}(x)}.

Polinomai f_{i}(x) ir \overline{f}_{i}(x) yra tarpusavyje pirminiai, todėl pagal Euklido algoritma_{‘} galime rasti tokius polinomus u_{i}(x) ir v_{i}(x), kad

u_{i}(x)f_{i}(x) + v_{i}(x)\overline{f}_{i}(x) = 1.

Tada

f(x) = u_{1}(x) \overline{f}_{1}(x) · c_{1}(x) + … + u_{n}(x) \overline{f}_{n}(x) c_{n}(x)

ir

f(x) ≡ u_{i}(x)\overline{f}_{i}(x) c_{i}(x) ≡ c_{i}(x) (mod f_{i}(x)),

nes \overline{f}_{j}(x) dalijasi iš f_{i}(x), kai j ≠ i. Taigi f(x) yra lyginiu_{‘} sistemos sprendinys.

△

13.4 teiginys. Tegu bekvadračio polinomo f(x) ∈ GF (q)[x] kanoninis skaidinys yra

f(x) = f_{1}(x)f_{2}(x) … f_{n}(x).

Tada bet kuriam kūno GF (q) elementu_{‘} rinkiniui (c_{1}, c_{2}, …, c_{n}) egzistuoja toks vienintelis polinomas h(x) ∈ GF (q)[x], kad

h(x) ≡ c_{i} (mod f_{i}(x)), 1 ⩽ i ⩽ n, deg h(x) < deg f(x),
h^{q}(x) ≡ h(x) (mod f(x)), deg h(x) < deg f(x)

ir tokiu_{‘} polinomu_{‘} h(x), tenkinančiu_{‘} paskutini_{‘} lygini_{‘}, yra lygiai q^{n}.

I_{‘} rodymas. Iš 13.3 teiginio žinome, kad bet kuriam kūno GF (q) elementu_{‘} rinkiniui (c_{1}, c_{2}, …, c_{n}) egzistuoja vienintelis polinomas h(x), kad

h(x) ≡ c_{i} (mod f_{i}(x)), 1 ⩽ i ⩽ n, deg h(x) < deg f(x).

Taigi

h^{q}(x) ≡ c_{i}^{q} ≡ c_{i} ≡ h(x) (mod f_{i}(x)), 1 ⩽ i ⩽ n

ir

h^{q}(x) ≡ h(x) (mod f(x)), deg h(x) < deg f(x).

Kita vertus, mes žinome, kad virš kūno GF (q) galioja lygybė (žr. 9.3 teigini_{‘})

x^{q} − x = ∏_{c∈GF (q)}(x − c),

todėl

h^{q}(x) − h(x) = ∏_{c∈GF (q)} (h(x) − c).

Bet jeigu h^{q}(x) ≡ h(x) (mod f(x)), tai

f_{i}(x) yra ∏_{c∈GF (q)} (h(x) − c) daliklis su visais i, 1 ⩽ i ⩽ n.

Polinomai f_{i}(x), 1 ⩽ i ⩽ n yra neredukuojami, todėl kiekvienam i atsiras toks c_{i} ∈ GF (q), kad

f_{i}(x) yra (h(x) − c_{i}) daliklis, t.y.
h(x) ≡ c_{i} (mod f_{i}(x)).
△

13.5 teiginys. Tegu f(x) yra unitarusis polinomas virš kūno GF (q), o h(x) ∈ GF (q)[x] – toks polinomas, kad h^{q}(x) ≡ h(x) (mod f(x)). Tada

f(x) = ∏_{c∈GF (q)} DBD (f(x), h(x) − c).

I_{‘} rodymas. Visi polinomai DBD(f(x), h(x) − c), c ∈ GF (q), yra polinomo f(x) dalikliai. Polinomai h(x) − c_{1} ir h(x) − c_{2} yra tarpusavyje pirminiai, kai c_{1} ≠ c_{2}, todėl tarpusavyje pirminiai bus ir polinomai DBD(f(x), h(x) − c_{1}) ir DBD(f(x), h(x) − c_{2}), kai c_{1} ≠ c_{2}. Taigi poromis tarpusavyje pirminiu_{‘} polinomu_{‘} sandauga

∏_{c∈GF (q)} DBD(f(x), h(x) − c)

yra polinomo f(x) daliklis.

Kita vertus, žinome, kad

x^{q} − x = ∏_{c∈GF (q)}(x − c),

todėl

h^{q}(x) − h(x) = ∏_{c∈GF (q)} (h(x) − c)

ir f(x) yra ∏_{c∈GF (q)} (h(x) − c) daliklis, todėl f(x) yra ∏_{c∈GF (q)} DBD(f(x),

h(x) − c) daliklis.

Bet du vienas kita_{‘} dalijantys unitarieji polinomai sutampa, todėl teiginys i_{‘}rodytas.

△

Iš 13.5 teiginio matome, kad norint rasti polinomo f(x) ∈ GF (q)[x] skaidini_{‘}, reiktu_{‘} rasti polinoma_{‘} h(x) ∈ GF (q)[x], tenkinanti_{‘} sa_{‘}lyga_{‘} h^{q}(x) ≡ h(x)(mod f(x)). Bekvadračiui polinomui f(x) tokio polinomo egzistavima_{‘} garantuoja 13.4 teiginys. Parodysime, kaip galima sukonstruoti 13.4 teiginyje esančius polinomus h(x).

Rasime lyginio

h^{q}(x) ≡ h(x) (mod f(x)), deg h < deg f  (∗)

sprendinius. Tegu h(x) = ∑_{i=0}^{n−1} a_{i}x^{i}; čia n = deg f(x) ir a_{i} ∈ GF (q).

Žinome, kad h^{q}(x) = ∑_{i=0}^{n−1} a_{i}x^{iq}, todėl,

jeigu

x^{iq} ≡ ∑_{j=0}^{n−1} b_{ij}x^{j} (mod f(x)), i = 0, 1, …, n − 1,

tai

h(x) ≡ h^{q}(x) ≡ ∑_{i=0}^{n−1} a_{i} ∑_{j=0}^{n−1} b_{ij}x^{j} = ∑_{j=0}^{n−1} ( ∑_{i=0}^{n−1} a_{i}b_{ij})x^{j} (mod f(x)).

Lyginys h^{q}(x) ≡ h(x) (mod f(x)) ekvivalentus lygybėms

a_{j} = ∑_{i=0}^{n−1} a_{i}b_{ij}, j = 0, 1, …, n − 1.

Jeigu matrica B = (b_{ij})_{0⩽i, j⩽n−1}, tai paskutinės lygybės ekvivalenčios matricu_{‘} lygybėms

\begin{matrix}(a_{0}, a_{1}, …, a_{n−1}) B = (a_{0}, a_{1}, …, a_{n−1}), \\ (a_{0}, a_{1}, …, a_{n−1}) (B − I) = (0, 0, …, 0); \end{matrix}  (∗∗)

čia I – vienetinė n × n matrica virš GF (q). Jau žinome, kad pastaroji homogeninė tiesiniu_{‘} lygčiu_{‘} sistema turi q^{k} sprendiniu_{‘}, t.y. sprendiniu_{‘} poerdvio dimensija yra lygi k, ir matricos B − I rangas lygus n − k; čia k – polinomo f(x) kanoniniame skaidinyje esančiu_{‘} neredukuojamu_{‘} polinomu_{‘} skaičius. Taigi matricos B − I rangas nustato polinomo f(x) kanoniniame skaidinyje esančiu_{‘} neredukuojamu_{‘} polinomu_{‘} skaičiu_{‘}. Jeigu k = 1, tai polinomo f(x) kanoniniame skaidinyje yra vienas neredukuojamas polinomas, t.y. pats polinomas f(x) neredukuojamas. Šiuo atveju sistemos (∗∗) sprendiniai yra eilutės (d, 0, …, 0), d ∈ GF (q).

Jeigu k > 1, tai sistemos (∗∗) fundamentalia_{‘}ja_{‘} sprendiniu_{‘} sistema_{‘}

d_{1} = (d_{10}, d_{11}, …, d_{1n−1}), …, d_{k} = (d_{k0}, d_{k1}, …, d_{kn−1})

atitinka baziniai lyginio (∗) polinomai

h_{j}(x) = ∑_{i=0}^{n−1} d_{ji}x^{i}.

Aišku, kad h_{1}(x) = 1, nes eilutė (1, 0, …, 0) yra sistemos (∗∗) sprendinys.

Pasirinke_{‘} polinoma_{‘} h_{2}(x), gausime polinomo f(x) skaidini_{‘}

f(x) = ∏_{c∈GF (q)} DBD(f(x), h_{2}(x) − c) = g_{1}(x) … g_{l}(x);  (∗ ∗ ∗)

čia g_{1}(x), …, g_{l}(x) – polinomai, kuriu_{‘} laipsniai didesni už 1. Jeigu l = k, tai visi g_{i}(x) yra neredukuojami polinomai ir (∗ ∗ ∗) yra polinomo f(x) kanoninis skaidinys. Jeigu l < k, tai pasirinke_{‘} polinoma_{‘} h_{3}(x), randame visu_{‘} polinomu_{‘} g_{i}(x), 1 ⩽ i ⩽ l, skaidinius

g_{i}(x) = ∏_{c∈GF (q)} (g_{i}(x), h_{3}(x)), 1 ⩽ i ⩽ l.

Ši_{‘} procesa_{‘} te_{‘}sime tol, kol negausime visu_{‘} k neredukuojamu_{‘} polinomo f(x) daugikliu_{‘}. Proceso baigtinuma_{‘} garantuoja kitas teiginys.

13.6 teiginys. Tegu f_{u}(x) ir f_{v}(x) yra bet kurie skirtingi neredukuojami polinomo f(x) dalikliai. Tada egzistuoja j ∈ ℕ ir c ∈ GF (q), kad

f_{u}(x) yra h_{j}(x) − c daliklis, bet
f_{v}(x) nėra h_{j}(x) − c daliklis.

I_{‘} rodymas. Iš 13.3 teiginio i_{‘}rodymo matome, kad kiekviena_{‘} bazini_{‘} polinoma_{‘} h_{i}(x), 1 ⩽ i ⩽ k, atitinka tokia eilutė c_{i} = (c_{i1}, c_{i2}, …, c_{ik}), kad

h_{i}(x) ≡ c_{is} (mod f_{s}(x)), 1 ⩽ s ⩽ k, 1 ⩽ i ⩽ k.

Tegu visiems i, 1 ⩽ i ⩽ k, c_{iu} = c_{iv}. Jeigu h(x) yra bet kuris lyginio h^{q}(x) ≡ h(x) (mod f(x)), deg (h) < deg (f) sprendinys, tai jis yra baziniu_{‘} sprendiniu_{‘} h_{1}(x), h_{2}(x), …, h_{k}(x) tiesinė kombinacija h(x) = α_{1}h_{1}(x) + … + α_{k}h(x), α_{i} ∈ GF (q). Tada

\begin{matrix}h(x) ≡ α_{1}c_{1u} + … + α_{k}c_{ku} (mod f_{u}(x)), \\ h(x) ≡ α_{1}c_{1v} + … + α_{k}c_{kv} (mod f_{v}(x)) \end{matrix}

ir

h(x) (mod f_{u}(x)) = h(x) (mod f_{v}(x)).

Tačiau eilute_{‘} (c_{1}, …, c_{k}), kai c_{u} = 0, c_{v} = 1, atitinkantis polinomas h(x) tenkina lyginius h(x) ≡ c_{i} (mod f_{i}(x)), 1 ⩽ i ⩽ k. Bet tai prieštarauja paskutinei lygybei, nes

h(x) (mod f_{u}(x)) = 0 ≠ 1 = h(x) (mod f_{v}(x)).

Taigi egzistuoja toks j, 1 ⩽ j ⩽ k, kad c_{ju} ≠ c_{jv} ir

h_{j}(x) ≡ c_{ju} (mod f_{u}(x)),
h_{j}(x) ≡ c_{jv} (mod f_{v}(x)),
h_{j}(x) ≢ c_{jv} (mod f_{u}(x)), t.y.
f_{v}(x) yra polinomo h_{j}(x) − c_{jv} daliklis, bet
f_{u}(x) nėra polinomo h_{j}(x) − c_{jv} daliklis.
△

Bekvadračio polinomo f(x) ∈ GF (q)[x] faktorizacijos proceso aptarima_{‘} apibendrina Berlekampo^{1} algoritmas.

1 E. R. Berlekamp, g. 1940, – amerikiečiu_{‘} matematikas

13.7 algoritmas. Žinoma: bekvadratis polinomas f(x) ∈ GF (q)[x], deg f(x) = n.

Rezultatas: algoritmas faktorizuoja polinoma_{‘} f(x) virš kūno GF (q).

1. Konstruojame matrica_{‘} B = (b_{ij})_{0⩽i,j⩽n−1}, skaičiuodami

x^{iq} ≡ ∑_{j=0}^{n−1} b_{ij} x^{j} (mod f(x)), 0 ⩽ i ⩽ n − 1.

2. Tiesinėje algebroje žinomais metodais randame matricos B − I branduolio baze_{‘} (fundamentalia_{‘}ja_{‘} homogeninės sistemos (a_{0}, a_{1}, …, a_{n−1}) · (B − I) = (0, 0, …, 0) sprendiniu_{‘} sistema_{‘}) d_{1} = (1, 0, …, 0), …, d_{k} = (d_{k0}, d_{k1}, …, d_{kn−1}). Skaičius k yra polinomo f(x) kanoniniame skaidinyje esančiu_{‘} neredukuojamu_{‘} polinomu_{‘} skaičius. Tegu S yra polinomo f(x) skaidinyje esančiu_{‘} polinomu_{‘} aibė.

Priskiriame S := {f(x)}, r := 1, t := 1.

3. Jeigu k = r, tai aibėje S esantys polinomai yra polinomo f(x) kanoninio skaidinio polinomai; skaičiavimai baigiami.

Jeigu k < r, tai t := t + 1 ir h(x) := ∑_{i=0}^{n−1} d_{ti}x^{i}.

4. Visiems g(x) ∈ E, deg g(x) > 1 ir visiems c ∈ GF (q) skaičiuojame polinomus: DBD (g(x), h(x) − c). Tegu T yra šiu_{‘} polinomu_{‘}, kuriu_{‘} laipsnis didesnis už 1, aibė.

Priskiriame S := (S − {g}) ∪ T; r := r − 1 + |T |. Pereiname prie 3.

△

13.8 pavyzdys. Faktorizuosime polinoma_{‘} f(x) = x^{8} +x^{6} +x^{4} +x+1 virš kūno GF (2). Šis polinomas yra bekvadratis, nes DBD (f, f′(x)) = 1. Taikome Berlekampo algoritma_{‘}

x^{0} ≡ 1
x^{2} ≡  x^{2}
x^{4} ≡  x^{4}
x^{6} ≡  x^{6}
x^{8} ≡ 1 + x + x^{4} + x^{6}
x^{10} ≡ 1 + x + x^{2} + x^{3} + x^{4}
x^{12} ≡  x^{2} + x^{3} + x^{4} + x^{5} + x^{6}
x^{14} ≡ 1 + x  + x^{3}  + x^{5}  + x^{7},

todėl matrica B yra

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

o matrica B − I yra

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

Matricos B − I rangas lygus 6 ir todėl polinomo f(x) kanoniniame skaidinyje virš GF (2) yra k = 8 − 6 = 2 neredukuojami polinomai. Sistemos (∗∗) sprendiniu_{‘} aibė yra

{(α, 0, β, β, β, 0, β, β) | α, β ∈ GF (2)}.

Fundamentaliuosius sprendinius d_{1} = (1, 0, 0, 0, 0, 0, 0, 0) ir d_{2} = (0, 0, 1, 1, 1, 0, 1, 1,) atitinka polinomai

\begin{matrix}h_{1}(x) = 1, \\ h_{2}(x) = x^{2} + x^{3} + x^{4} + x^{6} + x^{7}. \end{matrix}

Pasinaudoje_{‘} Euklido algoritmu, gausime

DBD(f(x), h_{2}(x)) = x^{5} + x^{4} + x^{2} + x + 1

ir

DBD(f(x), h_{2}(x) − 1) = x^{3} + x^{2} + 1.

Taigi polinomo f(x) kanoninis skaidinys yra

f(x) = x^{8} + x^{6} + x^{4} + x + 1 = (x^{5} + x^{4} + x^{2} + x + 1) (x^{3} + x^{2} + 1).