Příklad. Rozložte polynom f(x) = x^{4} + 1 ∈ F_{3}[x] na ireducibilní činitele. \underline{Řešení:}

Máme q = 3 a n = degf = 4. Platí f′(x) = x^{3} a NSD(f(x), f′(x)) = 1. Tedy f(x) nemá vícenásobné činitele.

Spočteme x^{jq} mod f(x) pro j = 0, …, n − 1.

x^{0} ≡ 1 mod f(x)
x^{3} ≡ x^{3} mod f(x)
x^{6} ≡ 2x^{2} mod f(x)
x^{9} ≡ x mod f(x)

Dostáváme tedy matici

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

Gaussovou eliminací ji přivedeme do odstupňovaného tvaru:

B − I = ( \begin{matrix}0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 2 \end{matrix} ) ∼ ( \begin{matrix}0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 0 \\ 0 & 2 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{matrix} ) ∼ ( \begin{matrix}0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} ) .

Báze nulového prostoru je např. (1, 0, 0, 0), (0, 1, 0, 1). Dostáváme tedy h_{2}(x) = x + x^{3}. Platí f(x) = ∏_{c∈F_{3}} NSD(f(x), h_{2}(x) − c), tedy spočteme

c = 0, pak NSD(x^{4} + 1, x^{3} + x) = 1
c = 1, pak NSD(x^{4} + 1, x^{3} + x − 1) = x^{2} + 2x + 2
c = 2, pak NSD(x^{4} + 1, x^{3} + x − 2) = x^{2} − 2x + 2

a f(x) = (x^{2} + 2x + 2) · (x^{2} − 2x + 2).

Co však dělat, je-li q >> n? V tom případě bude NSD(f(x), h(x) − c) = 1 pro většinu c ∈ F_{q}. Budeme postupovat podobně jako předtím. Začneme Berlekampovým algoritmem a řešíme soustavu (B − I)x = 0, najdeme bázi h_{1}(x) = 1, h_{2}(x), …, h_{k}(x). Buď h(x) jeden z těchto polynomů a f(x) = ∏_{c∈F_{q}} NSD(f(x), h(x)− c). Označme C = {c ∈ F_{q}; NSD(f(x), h(x) − c) ≠ 1}. Potom platí rovnost f(x) = ∏_{c∈C} NSD(f(x), h(x)−c). Odtud plyne, že f(x)| ∏_{c∈C}(h(x)−c). Označme G(y) = ∏_{c∈C}(y − c). Pak f(x)|G(h(x)).

Věta 7.4. Mezi všemi polynomy G(y) ∈ F_{q}[y], pro které platí f(x)|G(h(x)), má monický polynom G(y) nejmenší stupeň.

Důkaz. Označme {0} ≠ J = {g(y) ∈ F_{q}[y]; f(x)|g(h(x))} ⊆ F_{q}[y]. Snadno se ověří, že J je ideál v F_{q}[y]. Jsou-li g_{1}(y), g_{2}(y) ∈ J, pak f(x)|g_{1}(h(x)), f(x)|g_{2}(f(x)) a tedy i f(x)|(g_{1} − g_{2})(h(x)). Je-li k(y) ∈ F_{q}[y], pak také f(x)|k(h(x)) · g_{1}(h(x)).

Jelikož platí, že okruh T[x] je obor integrity hlavních ideálů pro libovolné těleso T, je F_{q}[y] obor integrity hlavních ideálů. Proto existuje G_{0}(y) ∈ J takový, že všechny polynomy v J jsou násobkem G_{0}(y). G_{0}(y) je monický polynom nejmenšího stupně v J. Speciálně G_{0}(y)|G(y) = ∏_{c∈C}(y − c), tedy G_{0}(y) = ∏_{c∈C_{1}}(y − c) pro nějaké C_{1} ⊆ C. Protože f(x)|G_{0}(h(x)) = ∏_{c∈C_{1}}(h(x) − c), platí f(x) = ∏_{c∈C_{1}} NSD(f(x), h(x) − c) a odtud plyne C_{1} = C a G_{0}(y) = G(y). □

Jak tuto větu využít? Označme m = |C|. Pak G(y) = ∏_{c∈C}(y − c) = ∑_{j=0}^{m} b_{j}y^{j} pro nějaké koeficienty b_{0}, b_{1}, …, b_{m−1} a b_{m} = 1. Dále platí f(x)|G(h(x)) = ∑_{j=0}^{m} b_{j}h^{j}(x). Proto platí 0 ≡ G(h(x)) mod f(x) = (∑_{j=0}^{m} b_{j}h^{j}(x)) mod f(x) = ∑_{j=0}^{m} b_{j}(h^{j}(x) mod f(x)) a tedy platí 0 = ∑_{j=0}^{m} b_{j}(h^{j}(x) mod f(x)).

Z vlastností G(y) (přesněji řečeno z valstnbosti, že G(y) je polynom nejmenšího stupně takový, že f(x)|G(h(x)))plyne, že posloupnost polynomů 1 = h^{0}(x) mod f(x), h(x) = h^{1}(x) mod f(x), h^{2}(x) mod f(x), …, h^{m−1}(x) mod f(x) je lineárně nezávislá. Dále z rovnosti f(x) = ∏_{c∈C} NSD(f(x), h(x) − c) plyne, že m ≤ k, kde k je počet ireducibilních činitelů v rozkladu f(x), protože počet činitelů na úravé straně poslední rovnosti (každý z nich má stupeň aspoň 1) nemůže být větší než počet různých irreducibilních dělitelů polynomu f(x).

Jak hledáme G(y)? Počítáme postupně h^{j}(x) mod f(x) a první index j, pro který platí, že h^{j}(x) mod f(x) je lineární kombinací h^{i}(x) mod f(x) pro i = 0, …, j−1, se rovná m. Koeficienty této lineární kombinace jsou b_{0}, b_{1}, …, b_{m−1}. Tak dostaneme polynom G(y), najdeme jeho kořeny C a pak dokončíme Berlekampův algoritmus. Berlekampův algoritmus s využitím polynomu G(y) se nazývá Zassenhausův algoritmus.

Příklad. Rozložte polynom f(x) = x^{6} − 3x^{5} + 5x^{4} − 9x^{3} − 5x^{2} + 6x + 7 ∈ F_{23}[x] pomocí Zassenhausenova algoritmu. \underline{Řešení:}

Máme n = degf = 6 a q = 23. Snadno spočteme, že platí NSD(f(x), f′(x)) = 1.

Začneme počítat Berlekampovým algoritmem. Spočteme x^{jq} mod f(x) pro j = 0, …, n − 1. Dostáváme matici

B = ( \begin{matrix}1 & 5 & −10 & 0 & 11 & −3 \\ 0 & 0 & 10 & 7 & 0 & 0 \\ 0 & −1 & 10 & 9 & −4 & −10 \\ 0 & 8 & 0 & −8 & 7 & 9 \\ 0 & −3 & 1 & 10 & 7 & 2 \\ 0 & −10 & −9 & −11 & 2 & −9 \end{matrix} )

Matice B−I má hodnost 3, báze nulového prostoru je např. h_{1} = (1, 0, 0, 0, 0, 0), h_{2} = (0, 4, 2, 1, 0, 0), h_{3} = (0, −2, 9, 0, 1, 1).

Nyní si vezměme např. h(x) = h_{2}(x) = x^{3} + 2x^{2} + 4x. Platí

h^{0}(x) ≡ 1 mod f(x)
h^{1}(x) ≡ x^{3} + 2x^{2} + 4x mod f(x)
h^{2}(x) ≡ 7x^{5} + 7x^{4} + 2x^{3} − 2x^{2} − 6x − 7 mod f(x)
h^{3}(x) ≡ −11x^{5} − 11x^{4} − x^{3} − 9x^{2} − 5x − 2 mod f(x)

Platí h^{3}(x)−5h^{2}(x)+11h(x)−10 ≡ 0 mod f(x), takže G(y) = y^{3}−5y^{2}+11y−10. Kořeny G(y) jsou −3, 2 − 6.

Zbývá spočítat

NSD(f(x), x^{3} + 2x^{2} + 4x + 3) = x − 4
NSD(f(x), x^{3} + 2x^{2} + 4x − 2) = x^{2} − x + 7
NSD(f(x), x^{3} + 2x^{2} + 4x − 6) = x^{3} + 2x^{2} + 4x − 6