Věta 5.4. Konečné těleso F_{q} je (q − 1)-ní cyklotomické rozšíření libovolného svého podtělesa.

Důkaz. Polynom x^{q} −1 ∈ K[x] pro libovolné podtěleso K ⊂ F_{q} se v F_{q} rozkládá na součin lineárních činitelů a nemůže se rozkládat na součin lineárních činitelů nad libovolným menším podtělesem F_{q}. □

Poznámka. F_{q}^{∗} je cyklická grupa řádu q −1. Pro každého dělitele n čísla q −1 existuje cyklická podgrupa {1, α, α^{2}, …, α^{n−1}} grupy F_{q}^{∗} řádu n. Prvky této grupy jsou n-té odmocniny z 1 nad každým podtělesem tělesa F_{q} a generátor α je primitivní n-tá odmocnina z 1 nad libovolným podtělesem tělesa F_{q}.

Lemma 5.5. Nechť d je dělitel čísla n a d < n. Potom Q_{n}(x) dělí \frac{x^{n}−1}{x−1}.

Důkaz. Platí Q_{n}(x) dělí x^{n} − 1 = (x^{d} − 1) · \frac{x^{n}−1}{x^{d}−1}. Je-li ξ primitivní n-tá odmocnina z 1, pak x − ξ|Q_{n}(x) a současně x − ξ nedělí (x^{d} − 1). Tedy x − ξ|\frac{x^{n}−1}{x^{d}−1}. □

6. Reprezentace prvků konečných těles

Jak reprezentovat prvky konečného tělesa, které má q = p^{k} prvků? V této kapitole uvedeme tři různé možnosti a budeme je pro názornost ilustrovat na tělese F_{9} = F_{3^{2}} . Pak pro reprezentaci tělesa F_{9} můžeme použit následující metody.

Příklad 1: Nejprve nějak uhodneme ireducibilní polynom stupně 2 nad F_{3}[x]. Je to např. f(x) = x^{2} + 1. Vezmeme kořenové rozšíření F_{3}[x] určené polynomem x^{2} + 1. Označme α nějaký kořen x^{2} + 1 v F_{q}[x]. Potom všechny prvky F_{q}(x) jsou 0, 1, 2, α, α + 1, α + 2, 2α, 2α + 1, 2α + 2.

\underline{Nevýhoda:} musíme nějak najít ireducibilní polynom stupně n v F_{p}[x], abychom uměli počítat v F_{p^{n}}.

Příklad 2: těleso F_{9} je 8. cyklotomické rozšíření tělesa F_{3}. Potřebujeme najít rozklad polynomu Q_{8}(x) = x^{4} +1 = (x^{2} +x+2)(x^{2} +2x+2) na ireducibilní činitele nad F_{3}. Označme ξ primitivní 8. odmocninu z 1. Potom F_{q} = {0, ξ, ξ^{2}, …, ξ^{8}}.

Izomorfismus mezi řešením z předchozího příkladu je dán tím, že ξ = α + 1, neboť pro α platí α^{2} + 1 = 0. Dále pak platí

ξ ∼ α + 1  ξ^{4} ∼ 2  ξ^{7} ∼ 2α
ξ^{2} ∼ 2α  ξ^{5} ∼ 2 + 2α  ξ^{8} ∼ 1
ξ^{3} ∼ 1 + 2α  ξ^{6} ∼ α

\underline{Nevýhoda:} Je třeba rozložit Q_{p^{k}−1}(x) na ireducibilní činitele nad F_{p}.

Příklad 3: Tato metoda je založena na doprovodné matici polynomu (companion matrix). Nechť f(x) = a_{0} + a_{1}x + … + a_{n−1}x^{n−1} + x^{n}, pak jeho doprovodná matice je matice

A = ( \begin{matrix}0 & 0 & 0 & … & 0 & −a_{0} \\ 1 & 0 & 0 & … & 0 & −a_{1} \\ 0 & 1 & 0 & … & 0 & −a_{2} \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & … & 0 & 1 & 0 & −a_{n−2} \\ 0 & … & 0 & 0 & 1 & −a_{n−1} \end{matrix} )

Pokud je f(x) monický ireducibilní polynom v F_{p}[x] a A je jeho doprovodná matice, pak platí f(A) = a_{0} · I + a_{1} · A + a_{2} · A^{2} + … + a_{n−1} · A^{n−1} + A^{n} = 0.

Pro f(x) = x^{2} + 1 ∈ F_{3}[x] je doprovodná matice A = ( \begin{matrix}0 & −1 \\ 1 & 0 \end{matrix} ) ∼ α. Platí

A^{2} = ( \begin{matrix}−1 & 0 \\ 0 & −1 \end{matrix} ) a A^{0} = E ∼ 1. Tedy

f(A) = A^{2} + I = ( \begin{matrix}−1 & 0 \\ 0 & −1 \end{matrix} ) + ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) = 0,

čili A lze pova6ovat za kořen polynomu x^{2} + 1

Platí α + 1 = A + I = ( \begin{matrix}1 & −1 \\ 1 & 1 \end{matrix} ).

Prvky tělesa F_{9} jsou potom matice 0, I, 2I, A, I + A, 2I + A, 2A, I + 2A, 2I + 2A. Přímým výpočtem se potom můžeme přesvědčit, že např. (2I + A)(I + 2A) = 2A.

K polynomu x^{2} + x + 2 ∈ F_{3}[x] je doprovodná matice ( \begin{matrix}0 & −2 \\ 1 & −1 \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & 2 \end{matrix} )

v F_{3}.

Tato matice je kořenem cyklotomického polynomu Q_{8}(x) = (x^{2} + x + 2)(x^{2} + 2X + 2) a prvky tělesa F_{9} pak jsou matice 0, C, C^{2}, C^{3}, C^{4}, C^{,}C^{5}, C^{6}, C^{7}, C^{8}.

7. Faktorizace polynomů nad konečnými tělesy

V dalším uvažujme monický polynom f(x) z F_{q}[x]. Chceme najít rozklad f(x) = f_{1}^{l_{1}}(x) · f_{2}^{l_{2}}(x) · . . . · f_{k}^{l_{k}}(x), kde f_{1}, …, f_{k} jsou ireducibilní a navzájem různé.

Na začátku spočteme f′(x) a NSD(f(x), f′(x)) = d(x). Pak jestliže

(1) d(x) = 1, pak l_{1} = l_{2} = … = 1,

(2) d(x) = f(x), pak f′(x) = 0 (protože degf′(x) < degf(x)), tedy při derivování se všechny členy vynulovali. To nastane právě tehdy, když jediné monočleny s nenulovám koeficientem v f(x) mají exponenty, které jsou násobkem p, kde p = char F_{q}. T.j. f(x) = a_{0} + a_{1}x^{p} + a_{2}x^{2p} + … + a_{k−1}x^{(k−1)p} + x^{kp} a tedy f(x) = g(x^{p}), kde g(y) = a_{0} + a_{1}y + … + a_{k−1}y^{k−1} + y^{k},

(3) degd(x) > 0 a degd(x) < n, potom f(x) = d(x) · \frac{f(x)}{d(x)} .

Věta 7.1. Nechť f ∈ F_{q}[x] je monický polynom, h ∈ F_{q}[x] takový, že h^{q} ≡ h mod f. Pak platí

f(x) = ∏_{c∈F_{q}} NSD(f(x), h(x) − c)

Důkaz. Pro všechna c ∈ F_{q} platí NSD(f(x), h(x) − c)|f(x). Pro různá c ∈ F_{q} jsou polynomy h(x) − c nesoudělné, proto jsou po dvou nesoudělné i polynomy NSD(f(x), h(x) − c). Tedy ∏_{c∈F_{q}} NSD(f(x), h(x) − c)|f(x).

Naopak f(x)|h^{q}(x) − h(x) = ∏_{c∈F_{q}} h(x) − c. Je-li f_{i}(x) libovolný ireducibilní činitel f(x), pak f_{i}|h(x) − c pro nějaké c ∈ F_{q}. Tedy f_{i}(x) dělí NSD(f(x), h(x) − c) pro vhodné c ∈ F_{q}. Proto f(x) = f_{1}(x) · f_{2}(x) ⋯ f_{k}(x)| ∏_{c∈F_{q}} NSD(f(x), h(x) − c). □

Zajímají nás takové polynomy h(x), pro které platí h^{q} ≡ h mod f a rozklad ∏_{c∈F_{q}} NSD(f(x), h(x)−c) je netriviální. Takovým polynomům h se říká f-redukující.

Snadno lze ověřit, že každý polynom h(x) ∈ F_{q}[x], pro který platí h^{q} ≡ h mod f a 0 < degh < degf, je f-redukující.