Dále se budeme zabývat tím, jak hledat f-redukující polynomy. Použijeme čínskou větu o zbytcích.

Předpokládejme, že f = f_{1} ⋯ f_{k} pro navzájem různé ireducibilní polynomy f_{1}, …, f_{k} a nechť degf = n. Zvolíme uspořádanou k-tici (c_{1}, …, c_{k}) prvků F_{q}. Podle čínské věty o zbytcích existuje právě jeden polynom h(x) ∈ F_{q}[x] stupně menšího než n takový, že h(x) ≡ c_{i} mod f_{i}(x) pro všechna i = 1, …, k. Pak h^{q}(x) ≡ c_{i}^{q} = c_{i} ≡ h(x) mod f_{i}(x) pro všechna i = 1, …, k, tedy f_{i}(x)|h^{q}(x) − h(x) pro všechna i = 1, …, k. Protože jsou f_{1}, …, f_{k} po dvou nesoudělné, platí f(x) = f_{1}(x) ⋯ f_{k}(x)|h^{q}(x) − h(x).

Je-li h(x) libovolný polynom stupně menšího než n, pak podle Věty 7.1 platí f(x) = ∏_{c∈F_{q}} NSD(f(x), h(x) − c). Pro libovolné i = 1, …, k platí f_{i}(x)|f(x) = ∏_{c∈F_{q}} NSD(f(x), h(x) − c). Protože f_{i}(x) je ireducibilní v F_{q}[x], existuje c_{i} ∈ F_{q} takový, že f_{i}(x)|NSD(f(x), h(x) − c_{i}). Tedy f_{i}(x)|h(x) − c_{i} a proto h(x) ≡ c_{i} mod f_{i}(x). Z jednoznačnosti existence takového polynomu h(x) (t.j. stupně menšího než n a kongruentního s konstantou c_{i} modulo f_{i}(x) pro i = 1, …, k), která je dána čínskou větou o zbytcích, pak plyne, že počet polynomů h(x), pro které platí h^{q}(x) ≡ h(x) mod f(x) a degh < n, je přesně q^{k}.

Jak tedy budeme postupovat? Předchozí odstavec a následující tvrzení nám dávají návod na algoritmus, který se nazývá Berlekampův algoritmus. Nejprve spočítáme x^{jq} mod f(x) pro j = 0, …, n − 1. Platí x^{jq} mod f(x) = ∑_{i=0}^{n−1} b_{ij}x^{i}, kde b_{ij} ∈ F_{q}. Označme B = (b_{ij}) (čtvercová matice řádu n).

Lemma 7.2. Polynom h(x) = a_{0}+a_{1}x+…+a_{n−1}x^{n−1} je řešením rovnice h^{q}(x) ≡ h(x) mod f(x) právě když platí

B · ( a_{0} ; a_{1} ; ⋮ ; a_{n−1} ) = ( a_{0} ; a_{1} ; ⋮ ; a_{n−1} ) ,

neboli (B − I) · ( a_{0} ; a_{1} ; ⋮ ; a_{n−1} ) = 0.

Důkaz. Platí B · ( a_{0} ; a_{1} ; ⋮ ; a_{n−1} ) = ( a_{0} ; a_{1} ; ⋮ ; a_{n−1} ) právě tehdy, když a_{i} = ∑_{j=0}^{n−1} b_{ij} · a_{j}

pro každé i = 0, …, n − 1 (z násobení matic). To je právě tehdy, když h(x) = ∑_{i=0}^{n−1} a_{i}x^{i} = ∑_{i=0}^{n−1}(∑_{j=0}^{n−1} b_{ij}a_{j}) · x^{i} = ∑_{j=0}^{n−1} a_{j} ∑_{i=0}^{n−1} b_{ij}x^{i} ≡ ∑_{j=0}^{n−1} a_{j}x^{jq} = ∑_{j=0}^{n−1} a_{j}^{q}x^{jq} = (∑_{j=0}^{n−1} a_{j}x^{j})^{q} = h^{q}(x) mod f(x) □

Stačí nám pak najít nějakou bázi nulového prostoru matice (B − I). Jeden prvek je (1, 0, …, 0), tomu odpovídá h_{1}(x) = 1. Doplníme ho do báze nulového prostoru a dostaneme tak další polynomy h_{2}(x), …, h_{k}(x).

Lemma 7.3. Jsou-li f_{1}, f_{2} dva různé ireducibilní faktory f(x), pak existuje polynom h_{j}(x) pro j = 2, …, k takový, že v součinu ∏_{c∈F_{q}} NSD(f(x), h_{j}(x) − c) polynomy f_{1}(x) a f_{2}(x) dělí různé činitele.

Důkaz. Platí, že h_{1}(x) = 1, tj. h_{1}(x) ≡ 1 mod f_{1}(x) a také h_{1}(x) ≡ modf_{2}(x). Předpokládejme dále, že h_{j}(x) ≡ c_{j1} mod f_{1}(x), h_{j}(x) ≡ c_{j2} mod f_{2}(x) a c_{j1} = c_{j2} pro každé j = 2, …, k. Pak libovolný polynom h(x) ∈ F_{q}[x] stupně menšího než n, pro který platí h(x)^{q} ≡ h(x) mod f(x) lze vyjádřit jako lineární kombinaci

h(x) = ∑_{j=1}^{k}a_{j}h_{j}(x)

pro nějaké koeficienty a_{j} ∈ F_{q}. Pak ale platí h(x) ≡ ∑_{j=1}^{k} a_{j}c_{j1} mod f_{1}(x) a h(x) ≡ ∑_{j=1}^{k} a_{j}c_{j2} mod f_{2}(x). Označíme-li c = ∑_{j=1}^{k} a_{j}c_{j1} ∈ F_{q} pak h(x) ≡ c mod f_{1}(x) a h(x) ≡ c mod f_{2}(x). To je ale ve sporu s tím, že podle čínské věty o zbytcích existuje polynom h(x) ∈ F_{q}[x] stupně menšího než n, pro který platí h(x) ≡ 0 mod f_{1}(x), h(x) ≡ 1 mod f_{2}(x) a h(x)^{q} ≡ h(x) mod f(x). □

Příklad. Rozložte polynom f(x) = x^{8} + x^{6} + x^{4} + x^{3} + 1 ∈ F_{2}[x] pomocí Berlekampova algoritmu. \underline{Řešení:}

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

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

x^{0} ≡ 1 mod f(x)
x^{2} ≡ x^{2} mod f(x)
x^{4} ≡ x^{4} mod f(x)
x^{6} ≡ x^{6} mod f(x)
x^{8} ≡ x^{6} + x^{4} + x^{3} + 1 mod f(x)
x^{10} ≡ x^{6} + x^{4} + x^{3} + 1 + x^{6} + x^{5} + x^{2} = x^{5} + x^{4} + x^{3} + x^{2} + 1 mod f(x)
x^{12} ≡ x^{7} + x^{6} + x^{5} + x^{4} + x^{2} mod f(x)
x^{14} ≡ x^{5} + x^{4} + x^{3} + x + 1 mod f(x)

Z toho dostáváme matici

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

Dále spočteme

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

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

Báze nulového prostoru je tedy (1, 0, 0, 0, 0, 0, 0, 0), (0, 1, 1, 0, 0, 1, 1, 1). Tedy h_{2}(x) = x+x^{2} +x^{5} +x^{6} +x^{7}. Platí NSD(f(x), h_{2}(x)) = x^{6} +x^{5} +x^{4} +x+1

a NSD(f(x), h_{2}(x) − 1) = x^{2} + x + 1.