KONEČNÁ TĚLESA

JÍŘÍ TŮMA

Obsah

1. Úvod 3 2. Struktura konečných těles 5 3. Kořeny ireducibilních polynomů 12 4. Stopy, normy a báze 15 5. Odmocniny z 1 a cyklotomické polynomy 19 6. Reprezentace prvků konečných těles 22 7. Faktorizace polynomů nad konečnými tělesy 24 8. Výpočet kořenů polynomů nad konečnými tělesy 29

1. Úvod

Definice. Těleso F je množina se dvěma operacemi +, ·, splňující axiomy: (A1) a + (b + c) = (a + b) + c pro libovolné a, b, c ∈ F (A2) a + b = b + a pro libovolné a, b ∈ F (A3) existuje 0 ∈ F tak, že pro všechna a ∈ F platí a + 0 = 0 + a = a (A4) pro všechna a ∈ F existuje −a ∈ F tak, že platí a + (−a) = (−a) + a = 0 (M1) a · (b · c) = (a · b) · c pro všechna a, b, c ∈ F (M2) a · b = b · a pro všechna a, b ∈ F (M3) existuje 1 ∈ F tak, že pro všechna a ∈ F platí 1 · a = a · 1 = a (M4) pro všechna a ≠ 0 existuje a^{−1} ∈ F tak, že platí a · a^{−1} = a^{−1} · a = 1 (D) a · (b + c) = a · b + a · c pro všechna a, b, c ∈ F (distributivita) (N) 0 ≠ 1 (netrivialita)

Je-li F konečná množina, pak F je konečné těleso.

V dalším textu postupně přejdeme od zápisu součinu dvou prvků a, b ∈ F ve tvaru a · b ke stručnému ab.

Příklad. Příkladem tělesa je ℤ_{p} s operacemi sčítání a násobení modulo p, kde p je prvočíslo a ℤ_{p} = {0, 1, …, p − 1}.

Jediné ne zcela zřejmé je dokázat existenci inverzního prvku. Jak se inverzní prvky hledají? Nechť p = 19997 a mějme číslo 16. Pak hledáme prvek 16^{−1}.

Pomocí rozšířeného Eukleidova algoritmu najdeme celá čísla a, b tak, že a·16+b· p = 1. Nalezené číslo a ale nemusí patřit do ℤ_{p} a proto není obecně ještě inverzním prvkem k 16 v ℤ_{p}. Najdeme proto dále nezáporný zbytek r při dělení čísla a číslem p. Číslo r je určené jednoznačně podmínkami a = p · q + r pro nějaké celé číslo q a 0 ≤ r < p. Dosazením a = p · q + r do rovnosti a · 16 + b · p = 1 pak dostaneme r · 16 + p · (16 · q + b) = 1 a tedy r · 16 ≡ 1 mod p. Protože nyní už platí r ∈ ℤ_{p}, je r hledaný inverz k 16.

Použitím Eukleidova algoritmu tedy dostáváme:

19997 = 1249 · 16 + 13
16 = 1 · 13 + 3
13 = 4 · 3 + 1

Teď spočteme vyjádření čísel a a b. Z prvé rovnice dostáváme 13 = 19997−1249·16. Z druhé rovnice dostáváme 3 = 16 − 1 · 13 a po dosazení vyjádření z prvé rovnice dostáváme 3 = 16−(19997−1249·16) = 1250·16−19997. Z třetí rovnice dostáváme 1 = 13 − 4 · 3 a po dosazení vyjádření z prvé a druhé rovnice dostáváme 1 = (19997 − 1249 · 16) − 4 · (1250 · 16 − 19997) = −6249 · 16 + 5 · 19997.

Hledaným číslem je −6249 + 19997 = 13748. Inverz k číslu 16 v ℤ_{19997} je tedy číslo 13748.

Příklad. Nechť p(x) = x^{3} + x + 1 ∈ ℤ[x]. Platí, že množina všech polynomů s koeficienty v ℤ_{2} stupně rovného nebo menšího než 2 s operacemi sčítání a násobení modulo x^{3} + x + 1 je těleso.

Vezměme polynom (x + 1). Chceme najít polynom (x + 1)^{−1} inverzní k (x + 1). Budeme postupovat podobně jako v předchozím příkladě. Pomocí Eukleidova algoritmu najdeme polynomy a(x), b(x) ∈ ℤ_{2}[x] takové, aby platilo a(x) · (x + 1) + b(x) · p(x) = 1.

x^{3} + x + 1 = (x + 1) · (x^{2} + x) + 1

Tedy (x + 1)^{−1} = x^{2} + x.

Tento postup funguje vždy, kdykoliv největší společný dělitel p(x) ∈ F[x] a libovolného nenulového polynomu z F[x] stupně menšího než je stupeň p(x), je roven 1.

Postup neplatí například pro polynom p(x) = x^{3} + x = x · (x^{2} + 1).

Definice. Polynom p(x) ∈ F[x], kde F je těleso, se nazývá ireducibilní nad F, pokud degp(x) ≥ 1 a kdykoliv p(x) = a(x).b(x) v F[x], pak buď a(x) nebo b(x) je konstanta.

Věta 1.1 (o existenci kořenového rozšíření tělesa F určeného ireducibilním polynomem p(x) ∈ F[x]). Nechť p(x) ∈ F[x] je polynom stupně n ireducibilní nad F. Pak množina všech polynomů z F[x] stupně menšího než n se sčítáním a násobením modulo n je těleso.

Důkaz. Všechny vlastnosti tělesa jsou zřejmé, až na vlastnost (M4). Pro ověření vlastnosti (M4) potřebujeme předpoklad, že p(x) je ireducibilní v F[x]. Pro každý polynom 0 ≠ f(x) ∈ F[x] stupně menšího než n platí, že NSD(f(x), p(x)) = 1, tedy existují polynomy a(x), b(x) ∈ F[x] takové, že a(x)f(x) + b(x)p(x) = 1. Po úpravě a vydělení polynomu a(x) polynomem p(x) se zbytkem dostáváme a(x) = p(x)q(x) + r(x), kde degr(x) < n a dosazení do rovnosti a(x)f(x) + b(x)p(x) = 1 dostaneme r(x)f(x) + p(x)(f(x)q(x) + b(x)) = 1. Polynom r(x) je tedy inverzní polynom k f(x). □

Definice. Je-li F těleso, pak nejmenší přirozené číslo n, pro které platí \underbrace{1 + 1 + … + 1}_{n} =

0, se nazývá charakteristika F.

Pokud žádné takové n neexistuje, pak říkáme, že F má charakteristiku 0.

Poznámka (opakování). Charakteristika libovolného tělesa je buď 0 nebo prvočíslo. Konečné těleso má vždy nenulovou charakteristiku.

Definice. Nejmenší podtěleso K tělesa F se nazývá prvotěleso tělesa F.

Poznámka. Jak prvotěleso v tělese F vypadá, závisí na charakteristice F.

(1) Je-li charakteristika F rovna prvočíslu p ≥ 2, musí v prvotělese ležet prvky 0, 1, 1 + 1, 1 + 1 + 1, …, \underbrace{1 + 1 + … + 1}_{p−1}, které jsou navzájem různé.

Značení:

\underbrace{1 + 1 + … + 1}_{k} = k.1

k.1 + l.1 = (k + l).1 = r.1 , kde r je zbytek po dělení k + l prvočíslem p (k.1) · (l.1) = (kl).1 = s.1, kde s je zbytek po dělení k + l prvočíslem p

Prvotěleso v F je izomorfní se ℤ_{p}.

(2) Je-li charakteristika F rovna 0, pak prvotěleso v F je izomorfní s tělesem ℚ.

2. Struktura konečných těles

Lemma 2.1. Nechť F je konečné těleso a K je podtěleso F, počet prvků K je q. Pak F má q^{m} prvků pro nějaké přirozené číslo m.

Důkaz. Všimněme si, že F je vektorový prostor nad K (je třeba ověřit axiomy vektorového prostoru). Ten má konečnou dimenzi m ≥ 1, neboť má pouze konečně mnoho prvků a tedy obsahuje konečnou generující množinu. Zvolíme bázi b_{1}, …, b_{m} v F. Potom každý prvek x ∈ F lze jednoznačně vyjádřit ve tvaru x = a_{1}b_{1} + a_{2}b_{2} + …+a_{m}b_{m}, kde a_{1}, a_{2}, …, a_{m} ∈ K. Takových lineárních kombinací je právě q^{m}. □

Věta 2.2. Každé konečné těleso má p^{k} prvků pro nějaké prvočíslo p a přirozené číslo k.

Důkaz. Označme K prvotěleso v F. Charakteristika F je p pro nějaké prvočíslo p, tedy K má p prvků. Zbytek plyne z Lemma 2.1. □

V dalším se budeme zabývat otázkou, zda pro každé prvočíslo p a přirozené číslo k existuje těleso s p^{k} prvky. Jestliže ano, kolik takových těles existuje?

Definice. Nechť E, F jsou dvě tělesa. Pak vzájemně jednoznačné zobrazení T : E → F je izomorfismus, jestliže pro libovolné dva prvky a, b ∈ E platí:

T (a + b) = T (a) + T (b)
T (a · b) = T (a) · T (b)

Pokud pro nějaké těleso K platí K ⊆ E ∩ F, pak izomorfismus T : E → F se nazývá K-izomorfismus, jestliže pro každé a ∈ K platí T(a) = a.

Příklad. Nechť F je těleso charakteristiky p > 0 a K je prvotěleso F. Pak zobrazení T : ℤ_{p} → K definované předpisem

T (k) = \underbrace{1 + 1 + … + 1}_{k} = k · 1

je izomorfismus. Je třeba ověřit podmínky z definice izomorfizmu.

Příklad. Nechť K je těleso a p(x) ∈ K[x] je ireducibilní polynom stupně n. Pak množina polynomů z K[x] stupně menšího než n s operacemi sčítání a násobení modulo p(x) je opět těleso, jak jsme si připomněli v úvodu předchozí kapitoly. Označíme jej E. Pro ty, co mají rádi ideály a faktorové okruhy (důkazy s nimi jsou jednodušší!) připomeňme, že E ≃ K[x]/(p).

Nechť p(x) = a_{n}x^{n} + a_{n−1}x^{n−1} + … + a_{1}x + a_{0}, kde a_{i} ∈ K. Prvky E jsou polynomy x, x^{3} − x + 1 + 1, …, mezi nimi jsou i konstanty a ∈ K. S konstantami se v obou tělesech K a E počítá stejně. Tedy K ⊆ E je podtěleso tělesa E.

Polynom p(x) nemá v K žádný kořen, pokud n > 1.

Poznámka. Nechť f(x) ∈ K[x] a a ∈ K je kořen f(x). Potom (x − a)|f(x).

Důkaz. Libovolný polynom f(x) můžeme napsat ve tvaru f(x) = q(x)·(x−a)+r(x), kde degr(x) < deg(x−a) = 1, takže r(x) je konstantní polynom. Protože a je kořen f(x), po dosazení do f(x) dostáváme 0 = f(a) = q(a)·(a−a)+r(a) = r(a). Protože je r(x) konstantní polynom a r(a) = 0, platí r(x) = 0 a tedy (x − a)|f(x). □

Příklad. Uvažujme polynom p(z) = a_{n}z^{n} + … + a_{1}z + a_{0} ∈ K[z]. Dosadíme-li z = x ∈ E, pak je hodnota p(x) nějaký prvek tělesa E, konkrétně je to p(x) = a_{n}x^{n} +…+a_{1}x+a_{0} ∈ E. Protože p(x) ≡ 0 mod p(x), platí p(x) = 0 ∈ E. Polynom p(z) má tedy v tělese E aspoň jeden kořen.

Definice. Nechť K je těleso a p(x) ∈ K[x] je polynom ireducibilní nad K. Potom těleso E ⊇ K se nazývá kořenové rozšíření K určené polynomem p(x), jestliže v E existuje nějaký kořen θ polynomu p(x) a každé podtěleso E, které obsahuje současně K a θ, se rovná E.

Věta 2.3 (O existenci a jednoznačnosti kořenového rozšíření tělesa K určeného ireducibilním polynomem p(x) ∈ K[x]). Nechť K je těleso a p(x) ∈ K[x] je polynom ireducibilní nad K. Potom existuje kořenové rozšíření E tělesa K určené polynomem p(x). Kořenové rozšíření je určeno jednoznačně až na K-izomorfismus.

Důkaz. (1) Nejprve dokážeme existenci kořenového rozšíření. V předchozích příkladech jsme si ukázali, že těleso E obsahující všechny polynomy stupně menšího než je stupeň p(x) s operacemi sčítání a násobení modulo p(x) je těleso obsahující K jako podtěleso a ukázali jsme si, že v něm existuje aspoň jeden kořen polynomu p(x). Nechť f(x) = b_{m}x^{m} + … + b_{1}x + b_{0} ∈ K[x], přičemž m je menší než je stupeň p(x). Pak takový polynom musí ležet v libovolném podtělese E obsahujícím x a K.

(2) Zbývá dokázat jednoznačnost. Nechť F ⊇ K je nějaké kořenové rozšíření K obsahující kořen θ polynomu p(x). Definujme zobrazení T : E → F předpisem T (f(x)) = f(θ), kde f(x) = b_{m}x^{m} + … + b_{1}x + b_{0} a f(θ) = b_{m}θ^{m} + … + b_{1}θ + b_{0}.

Chceme dokázat, že T je K-izomorfismus. Jestliže a ∈ K, potom T (a) = a.

Dokážeme, že T je homomorfismus. Nechť f(x), g(x) ∈ E jsou libovolné dva polynomy, f(x) = b_{m−1}x^{m−1} + … + b_{1}x + b_{0} a g(x) = c_{m−1}x^{m−1} + … + c_{1}x + c_{0}. Potom platí platí

T (f(x)) = ∑_{i=0}^{m−1} b_{i}θ^{i}, T (g(x)) = ∑_{i=0}^{m−1} c_{i}θ^{i},

\begin{aligned}T ((f + g)(x)) & = ∑_{i=0}^{m−1}(b_{i} + c_{i})θ^{i} = ∑_{i=0}^{m−1} b_{i}θ^{i} + ∑_{i=0}^{m−1} c_{i}θ^{i} = \\ & = T (f(x)) + T (g(x)). \end{aligned}

Podobně (důkaz ale vyžaduje více počítání!)

T (fg(x)) = T (f(x)) · T (g(x)).

Nyní dokážeme, že T je prosté zobrazení. Nechť f(x), g(x) ∈ E jsou navzájem různé polynomy z E takové, že T (f(x)) = T (g(x)). Pak ∑_{i=0}^{m−1} b_{i}θ^{i} = ∑_{i=0}^{m−1} c_{i}θ^{i}, t.j. ∑_{i=0}^{m−1}(b_{i} −c_{i})θ^{i} = 0. Takže θ je kořen polynomu 0 ≠ g(x) = (b_{m−1} − c_{m−1})x^{m−1} + … + (b_{1} − c_{1})x + (b_{0} − c_{0}) ∈ K[x], který musí mít stupeň aspoň 1. Prvek θ je ale také kořenem polynomu p(x) ∈ K[x]. Tedy θ je kořen polynomu d(x) := NSD(g(x), p(x)) ∈ K[x]. Pak d(x)|p(x) v K[x], přičemž 1 ≤ degd(x) < degp(x). To je však spor s předpokladem, že p(x) je ireducibilní v K[x].

Zbývá dokázat, že T je na F. Im T je podtěleso F obsahující K a θ. Protože F je kořenové rozšíření K určené p(x), platí Im T = F.

Jsou-li nyní F, G dvě kořenová rozšíření K určená polynomem p(x), pak existují K-izomorfismy T : E → F a U : E → G. Potom UT^{−1} : F → G je K-izomorfismus F a G.

□

Poznámka. Jsou-li F a G dvě kořenová rozšíření tělesa K určená ireducibilním polynomem p(x) ∈ K[x] a označíme-li θ ∈ F a σ ∈ G kořeny polynomu p(x), pak K-izomorfizmus UT^{−1} : F → G z posledního odstavce důkazu předchozí věty má vlastnost

UT^{−1}(θ) = U(x) = σ

Lemma 2.4. Nechť F je těleso charakteristiky p > 0. Pak pro libovolné a, b ∈ F a libovolné přirozené číslo k > 0 platí

(a + b)^{p^{k}} = a^{p^{k}} + b^{p^{k}}

Důkaz. Důkaz provedeme indukcí dle k.

(1) Nechť k = 1. Podle binomické věty platí (a + b)^{p} = a^{p} + \binom{p}{1}a^{p−1}b + \binom{p}{2}a^{p−2}b^{2} + … + \binom{p}{p−1}ab^{p−1} + b^{p}. Protože p|\binom{p}{i} pro i ∈ \{1, 2, …, p − 1\}, platí v tělese F, že \binom{p}{i}.1 = 0. Tedy také \binom{p}{i}a^{p−i}b^{i} = 0 v F a proto

(a + b)^{p} = a^{p} + b^{p}.

(2) Předpokládejme platnost tvrzení pro k−1, tedy (a+b)^{p^{k−1}} = a^{p^{k−1}} +b^{p^{k−1}}.

Potom platí (a + b)^{p^{k}} = ((a + b)^{p^{k−1}})^{p} = (a^{p^{k−1}} + b^{p^{k−1}})^{p} = a^{p^{k}} + b^{p^{k}}.
□

Lemma 2.5. Nechť F je konečné těleso s q prvky. Potom pro každé a ∈ F platí a^{q} = a.

Důkaz. Pro a = 0 lemma platí. Nechť a ≠ 0, pak vezmeme multiplikativní grupu F. Ta má q − 1 prvků. Protože řád libovolného prvku konečné grupy je dělitelem počtu prvků této grupy, tak platí a^{q−1} = 1. □

Věta 2.6. Nechť F je konečné těleso s q prvky a K je jeho podtěleso. Potom pro polynom x^{q} − x ∈ K[x] platí v F[x]

x^{q} − x = ∏_{a∈F}(x − a)

Důkaz. Podle Lemma 2.5 platí pro každý prvek a ∈ F, že a^{q} = a, tedy a^{q} − a = 0. Z toho plyne, že každý prvek a ∈ F je kořenem polynomu x^{q} − x, proto platí (x − a)|(x^{q} − x). Protože polynomy x − a jsou pro různá a ∈ F po dvou nesoudělné, platí taky ∏_{a∈F}(x − a)|(x^{q} − x).

Zbývá ještě dokázat rovnost polynomů. Oba polynomy mají stupeň q (protože F má q prvků) a vedoucí člen obou polynomů je x^{q}. Protože ∏_{a∈F}(x − a)|(x^{q} − x), oba polynomy se rovnají. □

Před následující definicí si ještě zavedeme nové označení. Je-li E rozšíření tělesa K a θ ∈ E, pak nejmenší podtěleso tělesa E obsahující (tj. průnik všech podtěles tělesa E obsahujících) podtěleso K a prvek θ budeme označovat K(θ). Druhou podmínku z definice kořenového rozšíření tělesa K určeného ireducibilním polynomem p(x) ∈ K[x] (že libovolné podtěleso E obsahující K a θ se rovná E) pak můžeme zapsat stručně jako K(θ) = E. Podobně označíme K(θ_{1}, θ_{2}, …, θ_{m}) nejmenší podtěleso tělesa E obsahující K a prvky θ_{1}, θ_{2}, …, θ_{m} ∈ E.

Definice. Nechť K je těleso, f(x) ∈ K[x]. Pak rozšíření E tělesa K nazýváme rozkladové rozšíření tělesa K určené polynomem f(x), pokud se polynom f(x) rozkládá v E[x] na součin lineárních polynomů a současně těleso E je nejmenší podtěleso E (vzhledem k inkluzi) obsahující K, nad kterým se f(x) rozkládá na součin lineárních činitelů. Jinak řečeno, pokud jsou θ_{1}, θ_{2}, …, θ_{m} ∈ E všechny kořeny polynomu f(x), pak K(θ_{1}, θ_{2}, …, θ_{m}) = E.

Je-li T : E → F izomorfizmus těles E a F, pak jej můžeme přirozeně rozšířit do izomorfizmu T : E[x] → F[x] oborů integrity polynomů jedné proměnné nad oběma tělesy pomocí předpisu

T (a_{n}x^{n}+a_{n−1}x^{n−1}+⋯+a_{1}x+a_{0}) = T (a_{n})x^{n}+T (a_{n−1})x^{n−1}+⋯+T (a_{1})x+T (a_{0}).

Je samozřejmě třeba ověřit, že takto definované zobrazení T : E[x] → F[x] je skutečně izomorfizmus. Speciálně, polynom p(x) ∈ E[x] je ireducibilni nad E, právě když je polynom T (p(x)) ireducibilni nad F.

Věta 2.7 (O existenci a jednoznačnosti rozkladového rozšíření). Pro každé těleso K a každý polynom f(x) ∈ K[x] stupně aspoň 1 existuje rozkladové rozšíření tělesa K určené polynomem f(x).

Každá dvě rozkladová rozšíření tělesa K určená polynomem f(x) jsou K-izomorfní.

Důkaz. (1) Nejprve dokážeme existenci. Nechť degf = n a f(x) = p_{1} · p_{2} ⋯ p_{k} je rozklad polynomu f(x) na součin polynomů ireducibilních v K[x]. Budeme postupovat indukcí podle n−k. Je-li n−k = 0, jsou všechny polynomy p_{1}, p_{2}, …, p_{n} lineární a těleso K je rozkladové rozšíření K určené polynomem f(x).

Nechť n − k > 0. Pak aspoň jeden z činitelů p_{i}(x) má stupeň aspoň 2. Nechť to je p_{1}(x). Označme G kořenové rozšíření tělesa K určené polynomem p_{1}(x). V G[x] se p_{1}(x) rozkládá na součin aspoň dvou ireducibilních polynomů. Vezměme rozklad f(x) = q_{1} · q_{2} ⋯ q_{l} na součin ireducibilních polynomů v G[x]. Platí l > k, tedy n − l < n − k.

Nyní zformulujeme indukční předpoklad: pro každé rozšíření G tělesa K takové, že f(x) = q_{1} · q_{2} ⋯ q_{l} v G[x] a n − l < n − k, existuje rozkladové rozšíření E tělesa G určené f(x).

Tedy podle indukčního předpokladu existuje rozkladové rozšíření E tělesa G určené polynomem f(x). Těleso E je tedy rozšířením tělesa K, nad kterým se polynom f(x) rozkládá na součin lineárních činitelů. Nyní ještě musíme ověřit podmínku minimality, aby to bylo také rozkladové rozšíření tělesa K určené polynomem f(x). Nad tělesem E se polynom f(x) rozkládá na součin lineárních činitelů f(x) = a(x−θ_{1}) ⋯ (x−θ_{k}). Označme F nejmenší podtěleso tělesa E obsahující K a θ_{1}, …, θ_{k}, tj. F = K(θ_{1}, …, θ_{k}). Pak F splňuje oba požadavky na rozkladové rozšíření K určené polynomem f(x).

(2) Zbývá dokázat jednoznačnost. Ve skutečnosti dokážeme silnější tvrzení v podobě:

Jsou-li G a H rozšíření téhož tělesa K, zobrazení T : G → H je Kizomorfizmus a f(x) ∈ G[x], pak jsou K-izomorfní také rozkladové rozšíření G určené polynomem f(x) a rozkladové rozšíření H určené polynomem T (f(x)).

Také v tomto případě budeme předpokládat, že degf = n a že f = p_{1} · p_{2} ⋯ p_{k} je rozklad polynomu f(x) na součin polynomů ireducibilních v G[x] a budeme postupovat indukcí podle n−k. Protože rozšířené zobrazení T : G[x] → H[x] je izomorfizmus, je také T (f) = T (p_{1})T (p_{2}) ⋯ T (p_{k}) rozklad na součin polynomů ireducibilních v H[x]. Označme E rozkladové rozšíření G určené polynomem f(x) a F rozkladové rozšíření H určené polynomem T (f(x)).

Je-li n − k = 0, pak je E = G, F = H a T : G → H je K-izomorfizmus. Nechť n − k > 0 a nechť degp_{1} > 1. Potom polynom p_{1}(x) má v E

nějaký kořen α a v F má nějaký kořen β. Pak E(α) je kořenové rozšíření tělesa G určené polynomem p_{1}(x) a F(β) je kořenové rozšíření tělesa H určené polynomem T (p_{1}). Podle věty o existenci a jednoznačnosti kořenového rozšíření existuje K-izomorfizmus U : G(α) → H(β). Větu o existenci a jednoznačnosti kořenového rozšíření jsme sice nedokázali v té obecnosti, v jaké jsme ji právě použili, ale původní formulaci a důkaz lze snadno zobecnit do potřebného tvaru.

Je-li f = q_{1}q_{2} ⋯ q_{l} rozklad na polynomy ireducibilní nad G[x], pak platí l > k a tedy n − l < n − k.

Nyní zformulujeme indukční předpoklad. Pro libovolná dvě K-izomorfní rozšíření E′, F′ tělesa K, izomorfizmus T : E′ → F′ a libovolný polynom f(x) ∈ E′[x], který se nad E′ rozkládá na více ireducibilních polynomů než nad E, jsou rozkladová rozšíření F′ určené f a G′ určené T(f) K-izomorfní.

Podle indukčního předpokladu použitého na tělesa E′ = G(α), a F′ = H(β), na izomorfizmus U : E′ → F′ a na polynom f(x) tedy existuje Kizomorfismus F a G.

□

Věta 2.8 (O existenci a jednoznačnosti konečných těles). Pro každé prvočíslo p a přirozené číslo n existuje těleso s q = p^{n} prvky.

Libovolná dvě tělesa s p^{n} prvky jsou izomorfní (a jsou izomorfní rozkladovému rozšíření tělesa ℤ_{p} určeného polynomem x^{q} − x ∈ ℤ_{p}[x]).

Důkaz. Nejprve dokážeme existenci takového tělesa. Buď F rozkladové rozšíření ℤ_{p} určené polynomem x^{q} − x ∈ ℤ_{p}[x]. Polynom f(x) := x^{q} − x nemá v F vícenásobný kořen, protože (x^{q} − x)′ = q.x^{q−1} − 1 = −1, tedy NSD(f, f′) = 1 a proto f nemůže mít v F vícenásobný kořen. Tedy x^{q} − x má v F přesně q = p^{n} kořenů. Označme G = {a ∈ F : a^{q} − a = 0}. Ukážeme, že G je podtěleso F. Platí 0, 1 ∈ G a pro všechny a, b ∈ G platí (a.b)^{q} = a^{q}.b^{q} = a.b a (a + b)^{p^{k}} = a^{p^{k}} + b^{p^{k}} = a + b. Tedy G je podtěleso F, které obsahuje ℤ_{p} a nad kterým se x^{q} − x rozkládá na součin lineárních činitelů. Protože F je rozkladové rozšíření tělesa ℤ_{p} určené polynomem x^{q} − x, platí F = G a F má tedy q prvků.

Zbývá dokázat jednoznačnost. Nechť E je těleso s q = p^{n} prvky. Pak podle Věty 2.6 platí x^{q} − x = ∏_{a∈F}(x − a). Tedy E je rozkladové rozšíření ℤ_{p} určené polynomem x^{q} − x ∈ ℤ_{p}. Podle Věty 2.7 jsou libovolná dvě rozkladová rozšíření tělesa ℤ_{p} určená polynomem x^{q} − x izomorfní. □

Věta 2.9 (O podtělesech konečných těles). Nechť F_{q} je konečné těleso, q = p^{n}. Pak každé podtěleso tělesa F_{q} má p^{m} prvků pro nějaké m, které dělí n.

Pro každé m|n existuje právě jedno podtěleso tělesa F_{q}, které má p^{m} prvků.

Důkaz. Nejprve dokážeme první část věty. Je-li G podtěleso F_{p^{n}}, má také charakteristiku p a tedy p^{m} prvků pro nějaké m ≤ n. Navíc p^{n} musí být podle Lemma 2.1 mocninou p^{m}, čili m|n.

Zbývá dokázat druhou část věty. Těleso F_{p^{n}} je rozkladové rozšíření F_{p} určené polynomem x^{p^{n}} − x ∈ F_{p}[x]. Ukážeme napřed, že z předpokladu m|n plyne, že (x^{p^{m}} − x)|(x^{p^{n}} − x), neboli (x^{p^{m}−1} − 1)|(x^{p^{n}−1} − 1). Platí (p^{m} − 1)|(p^{n} − 1), neboť z n = k·m plyne (p^{km}−1) = (p^{m}−1)(p^{(k−1)m} +p^{(k−2)m} +⋯+p^{m}+1). Pokud a = b·c, pak (x^{bc} −1) = (x^{b} −1)(x^{(c−1)b} +x^{(c−2)b} +…+x^{b} +1). Tedy (x^{p^{m}−1}−1)|(x^{p^{n}−1}−1) a tedy (x^{p^{m}} − x)|(x^{p^{n}} − x). Každý kořen polynomu x^{p^{m}} − x je proto také kořenem polynomu x^{p^{n}} − x a leží tedy v F_{p^{n}}. Tedy x^{p^{m}} − x se nad F_{p^{n}} rozkládá na součin lineárních činitelů, proto F_{p^{n}} obsahuje rozkladové rozšíření F_{p} určené polynomem x^{p^{m}} − x, t.j. F_{p^{m}}. Dvě různá podtělesa mohutnosti p^{m} by obsahovala dohromady více než p^{m} kořenů polynomu x^{p^{m}} − x, což nelze. □

Příklad. Podtělesa F_{2^{30}} jsou F_{2}, F_{2^{2}} , F_{2^{3}} , F_{2^{5}} , F_{2^{6}} , F_{2^{10}} , F_{2^{15}} , F_{2^{30}} .

Pomocí Haaseova diagramu můžeme znázornit, jak jsou obsažena jedno v druhém.

[figure: F_{2}; F_{2^{2}}; F_{2^{3}}; F_{2^{5}}; F_{2^{6}}; F_{2^{10}}; F_{2^{15}}; F_{2^{30}}]

Věta 2.10. Multiplikativní grupa F_{q}^{∗} konečného tělesa F_{q} je cyklická.

Důkaz. Položme h = q − 1 = p_{1}^{r_{1}} · p_{2}^{r_{2}} · · · · · p_{k}^{r_{k}}. Polynom x^{h/p_{i}} − 1 má v F_{q} nejvýše \frac{h}{p_{i}} < h nenulových kořenů, proto existuje 0 ≠ a_{i} ∈ F_{q} (neboli a_{i} ∈ F_{q}^{∗}) takové,

že a_{i}^{h/p_{i}} ≠ 1. Položme b_{i} = a_{i}^{h/p_{i}^{r_{i}}} ≠ 1. Spočteme řád b_{i}. Platí b_{i}^{p_{i}^{r_{i}}} = a_{i}^{h} = 1

(neboť řád a_{i} dělí počet prvků F_{q}^{∗}, t.j. h = q − 1). Protože b_{i}^{p_{i}^{r_{i}−1}} = a_{i}^{h/p_{i}} ≠ 1, je řád b_{i} rovný p_{i}^{r_{i}}. Položme b = b_{1}b_{2} ⋯ b_{k}. Platí b^{h} = 1. Dále pro i = 1, 2, …, k platí b^{h/p_{i}} = ∏_{j=1}^{k} b_{j}^{h/p_{i}}. Je-li j ≠ i, tak p_{j}^{r_{j}} dělí \frac{h}{p_{i}} a tedy b_{j}^{h/p_{i}} = 1. Proto

b^{h/p_{i}} = b_{i}^{h/p_{i}} ≠ 1, neboť p_{i}^{r_{i}} ∤ \frac{h}{p_{i}} a p_{i}^{r_{i}} je řád b_{i}. Takže řád b je rovný h. □

Definice. Libovolný generátor F_{q}^{∗} se nazývá primitivní prvek F_{q}.

Příklad. Kolik primitivních prvků má těleso F_{q}? Tolik, kolik je čísel menších než q − 1 nesoudělných s q − 1, t.j. φ(q − 1), kde φ je Eulerova funkce.

Připomeňme si, že jsou-li F ⊆ E dvě tělesa a α ∈ E je algebraický nad F, pak monický polynom g z F[x] nejmenšího stupně, jehož kořenem je α, nazýváme minimální polynom prvku α. Pro polynom f ∈ F[x] platí, že f(α) = 0 právě tehdy, když g|f.

Věta 2.11. Nechť F_{q} ⊆ F_{r} jsou konečné tělesa a α je primitivní prvek F_{r}. Potom F_{r} = F_{q}(α).

Důkaz. Jelikož F_{q}(α) musí obsahovat 0 a všechny mocniny α, obsahuje taky všechny nenulové prvky F_{r}. □

Věta 2.12. Nechť F_{q} je konečné těleso a n je přirozené číslo. Pak existuje ireducibilní polynom f(x) ∈ F_{q}[x] stupně n.

Důkaz. Nechť α je primitivní prvek F_{q^{n}}. Víme, že F_{q} ⊆ F_{q^{n}}. Prvek α je kořenem nějakého polynomu f(x) ∈ F_{q}[x]. To plyne z toho, že F_{q^{n}} je vektorový prostor nad F_{q} a má nějakou konečnou dimenzi k (ve skutečnosti k = n). Proto jsou prvky 1 = α^{0}, α^{1}, α^{2}, …, α^{k} lineárně závislé a tedy existují prvky a_{0}, a_{1}, …, a_{k} ∈ F_{q} takové, že a_{0} · 1 + a_{1} · α + a_{2} · α^{2} + ⋯ + a_{k} · α^{k} = 0. Tedy α je kořenem polynomu f(x) = a_{0} + a_{1}x + … + a_{k}x^{k} ∈ F_{q}[x]. Buď g ∈ F_{q}[x] minimální polynom prvku α ∈ F_{q^{m}}, tedy g je ireducibilní nad F_{q}. Tedy F_{q^{n}} obsahuje kořenové rozšíření F_{q} určené polynomem g(x). Protože F_{q^{n}} = F_{q}(α), je tím kořenovým rozšířením celé těleso F_{q^{n}}. Odtud plyne, že degg = n. □

3. Kořeny ireducibilních polynomů

Lemma 3.1. Nechť f ∈ F_{q}[x] je ireducibilní polynom nad F_{q} a E ⊇ F_{q} je nějaké rozšíření obsahující kořen α polynomu f. Pak pro libovolný polynom h ∈ F_{q}[x] platí h(α) = 0 právě tehdy, když f|h.

Důkaz. Nechť a je vedoucí koeficient polynomu f(x), pak a^{−1}f(x) je monický polynom, jehož kořenem je α. Označme g ∈ F_{q}[x] minimální polynom prvku α. Potom g(x)|a^{−1}f(x). Protože f(x) je ireducibilní, platí g(x) = a^{−1}f(x). Proto f(x) dělí každý polynom h ∈ F_{q}[x], jehož kořenem je α. □

Lemma 3.2 (O zamrzlém kýblu). Nechť f ∈ F_{q}[x] je ireducibilní polynom stupně m. Potom platí f(x)|(x^{q^{n}} − x) právě tehdy, když m|n.

Důkaz. (⇐) Nechť f(x)|(x^{q^{n}} − x). Buď E kořenové rozšíření F_{q} určené polynomem f(x) a nechť v E leží kořen α polynomu f(x). Proto je α také kořenem polynomu x^{q^{n}} − x. Tedy F_{q^{n}} (rozkladové rozšíření F_{q} určené polynomem x^{q^{n}} − x) obsahuje kořen α polynomu f(x) a tedy i F_{q}(α) (kořenové rozšíření F_{q} určené polynomem f(x)). Těleso E = F_{q}(α) má q^{m} prvků a je podtělesem F_{q^{n}}, tedy m|n.

(⇒) Nechť m|n. Pak F_{q^{m}} je podtělesem F_{q^{n}} a F_{q^{m}} je kořenové rozšíření F_{q} určené polynomem f(x), tedy obsahuje kořen α polynomu f(x). Proto α ∈ F_{q^{n}} a platí α^{q^{n}}−α = 0, neboli α je kořen polynomu x^{q^{n}}−x ∈ F_{q}[x]. Protože také f(α) = 0 a NSD(f(x), x^{q^{n}} −x) = f(x) (protože f(x) je ireducibilní), platí f(x)|(x^{q^{n}} −x). □

Věta 3.3. Nechť f je ireducibilní polynom nad F_{q} stupně m. Potom f má v F_{q^{m}} nějaký kořen α, prvky α, α^{q}, α^{q^{2}}, …, α^{q^{m−1}} jsou navzájem různé a tvoří množinu všech kořenů polynomu f.

Důkaz. Kořenové rozšíření F_{q} určené polynomem f má q^{m} prvků a tedy se rovná F_{q^{m}}. Je-li β ∈ F_{q^{m}} a f(x) = a_{m}x^{m} + a_{m−1}x^{m−1} + … + a_{1}x + a_{0}, pak f(β)^{q} = (a_{m}β^{m} +…+a_{1}β +a_{0})^{q} = a_{m}^{q}(β^{m})^{q} +a_{m−1}^{q}(β^{m−1})^{q} +…+a_{1}^{q}β^{q} +a_{0}^{q} = a_{m}(β^{q})^{m} + a_{m−1}(β^{q})^{m−1} + … + a_{1}β^{q} + a_{0} = f(β^{q}). Je-li tedy α ∈ F_{q^{m}} kořen polynomu f(x), pak taky α, α^{q}, α^{q^{2}}, …, α^{q^{m−1}} jsou kořeny polynomu f(x).

Zbývá ješte dokázat, že jsou navzájem různé. Nechť α^{q^{i}} = α^{q^{j}} pro nějaké 0 ≤ i < j ≤ m − 1. Umocněním na q^{m−j} dostáváme (α^{q^{i}})^{q^{m−j}} = (α^{q^{j}})^{q^{m−j}}, tedy α^{q^{m−j+i}} = α^{q^{m}} = α. Tedy α je kořenem polynomu α^{q^{m−j+i}} − α a podle Lemma 3.2 platí m|m − j + i. Ovšem 0 < m − j + i < m, což je spor. □

Důsledek 3.4. F_{q^{m}} je rozkladové rozšíření F_{q} určené libovolným ireducibilním polynomem f ∈ F_{q}[x].

Důkaz. Polynom f se v F_{q^{m}} rozkládá na součin lineárních činitelů a tedy F_{q^{m}} obsahuje rozkladové rozšíření F_{q} určené polynomem f.

Naopak rozkladové rozšíření F_{q} určené polynomem f musí obsahovat kořenové rozšíření F_{q} určené polynomem f, které se rovná F_{q^{m}}. Rozkladové rozšíření F_{q} určené polynomem f dostaneme jako F_{q}(α, α^{q}, α^{q^{2}}, …, α^{q^{m−1}}) = F_{q}(α) = F_{q^{m}}.

□

Důsledek 3.5. Rozkladová rozšíření F_{q} určená dvěma ireducibilními polynomy téhož stupně jsou izomorfní.

Důkaz. Obě jsou izomorfní s F_{q^{m}}. □

Definice. Jsou-li F_{q^{m}} ⊇ F_{q} konečná tělesa a α ∈ F_{q^{m}}, pak prvky α, α^{q}, α^{q^{2}}, …, α^{q^{m−1}} se nazývají konjugované k α nad F_{q}.

Je-li F_{q} prvotěleso tělesa F_{q^{m}}, pak prvky α, α^{q}, α^{q^{2}}, …, α^{q^{m−1}} se nazývají absolutně konjugované k α nad F_{q}.

Poznámka. Je-li α ∈ F_{q^{m}}, platí α^{q^{m}} − α = 0. Pak pro minimální polynom f(x) prvku α nad F_{q} platí f(x)|x^{q^{m}} − x, tedy pro degf = d platí d|m.

Pokud d = m, jsou prvky α, α^{q}, α^{q^{2}}, …, α^{q^{m−1}} navzájem různé. Je-li d je vlastní

dělitel m, potom \underbrace{α, α^{q}, α^{q^{2}}, …, α^{q^{d−1}}}_{navzájem různé}, α^{q^{d}} = α, α^{q^{d+1}} = α^{q}, …, α^{q^{m−1}} = α^{q^{d−1}},

tedy každý z navzájem různých prvků α, α^{q}, α^{q^{2}}, …, α^{q^{d−1}} se opakuje přesně \frac{m}{d}- krát.

Věta 3.6. Prvky konjugované k α ∈ F_{q^{m}} nad F_{q} mají stejný řád v multiplikativní grupě F_{q^{m}} tj. v grupě F_{q^{m}}^{∗}.

Důkaz. Víme, že je-li G cyklická grupa řádu n a a ∈ G je její generátor, potom řád prvku a^{k} se rovná \frac{n}{NSD (n,k)} . Grupa F_{q^{m}}^{∗} je cyklická grupa řádu q^{m} − 1. Prvek α je generátor nějaké cyklické podgrupy G grupy F_{q^{m}}^{∗} řádu n|q^{m} − 1. Tedy řád α^{q} se rovná \frac{n}{NSD (q,n)} . Protože NSD(q, q^{m} − 1) = 1 a n|q^{m} − 1, platí také NSD(q, n) = 1. Řád α^{q} se proto rovná n. □

Důsledek 3.7. Je-li α ∈ F_{q^{m}} primitivní prvek F_{q^{m}}, pak všechny prvky konjugované k α nad F_{q} jsou také primitivní prvky v F_{q^{m}} (tedy je-li α ∈ F primitivní prvek F, pak všechny prvky konjugované k α nad libovolným podtělesem K ⊆ F jsou také primitivní prvky v F).

Příklad. Uvažujme těleso F_{16} a polynom f(x) = x^{4} + x + 1 ∈ F_{2}[x]. Vezměme kořen α ∈ F_{16} polynomu f(x). Pak prvky konjugované nad F_{2} jsou α, α^{2}, α^{4} = α + 1, α^{8} = (α + 1)^{2} = α^{2} + 1. Prvky konjugované nad F_{4} jsou α, α^{4} = α + 1.

Definice. Automorfismus σ tělesa F_{q^{m}} se nazývá automorfismus nad F_{q}, pokud platí σ(α) = α pro libovolné α ∈ F_{q}.

Poznámka. Každý automorfismus F je automorfismus nad prvotělesem F.

Věta 3.8. Nechť F_{q^{m}} a F_{q} jsou tělesa, pak zobrazení σ_{i} pro i = 0, 1, 2, …, m − 1 definovaná předpisem σ_{i}(α) = α^{q^{i}} pro α ∈ F_{q^{m}} jsou navzájem různá a tvoří všechny automorfismy F_{q^{m}} nad F_{q}.

Důkaz. Pro libovolné i = 0, 1, 2, …, m − 1 platí σ_{i}(αβ) = (αβ)^{q^{i}} = α^{q^{i}}β^{q^{i}} = σ_{i}(α)σ_{i}(β) a σ_{i}(α + β) = (α + β)^{q^{i}} = α^{q^{i}} + β^{q^{i}} = σ_{i}(α) + σ_{i}(β). Dále σ_{i}(α) = 0 právě tehdy, když α = 0. Tedy σ_{i} je automorfismus F_{q^{m}}. Je-li α ∈ F_{q}, potom σ_{i}(α) = α^{q^{i}} = α. Tedy σ_{i} je automorfismus nad F_{q}.

Nechť σ je libovolný automorfismus F_{q^{m}} nad F_{q}, β ∈ F_{q^{m}} primitivní prvek tělesa F_{q^{m}} a f(x) je minimální polynom β nad F_{q}. Polynom f(x) musí mít stupeň m. Označme f(x) = x^{m} + a_{m−1}x^{m−1} + … + a_{1}x + a_{0}. Platí 0 = β^{m} + a_{m−1}β^{m−1} + … + a_{1}β + a_{0} a tedy také 0 = σ(0) = σ(β^{m} + a_{m−1}β^{m−1} + … + a_{1}β + a_{0}) = σ(β^{m}) + σ(a_{m−1})σ(β^{m−1}) + … + σ(a_{1})σ(β) + σ(a_{0}) = σ(β^{m}) + a_{m−1}σ(β^{m−1}) + … + a_{1}σ(β) + a_{0} = f(σ(β)). Platí σ(β) = β^{q^{i}} pro nějaké i = 0, 1, …, m − 1. Pak σ(β^{k}) = (β^{k})^{q^{i}} pro libovolné k = 1, …, q^{m} − 1, neboli σ(α) = α^{q^{i}} = σ_{i}(α) pro každé 0 ≠ α ∈ F_{q^{m}} a rovněž pro α = 0. □

14 JÍŘÍ TŮMA

Všimněte si, že platí:

σ = σ_{1}

σ ∘ σ(α) = σ(α^{q}) = α^{q^{2}} = σ_{2}

σ ∘ σ ∘ σ(α) = σ_{3}

Důsledek 3.9. Grupa automorfismů F_{q^{m}} nad F_{q} je cyklická grupa řádu m. Grupa automorfismů F_{p^{k}} je cyklická grupa řádu k.

4. Stopy, normy a báze

Připomeňme si, že je-li F_{q^{m}} ⊇ F_{q}, tak všechny automorfismy F_{q^{m}} nad F_{q} jsou tvaru α → α^{q^{i}} pro i = 0, 1, 2, …, m − 1 a libovolné α ∈ F_{q^{m}}.

V dalším bude často používat označení F = F_{q^{m}} a K = F_{q}.

Definice. Nechť F = F_{q^{m}}, K = F_{q} a α ∈ F. Pak definujeme prvek Tr_{F/K} (α) = α + α^{q} + α^{q^{2}} + … + α^{q^{m−1}} a nazýváme ho stopa α nad K.

Je-li K prvotěleso v F, potom zapisujeme Tr_{F/K} (α) = Tr_{F}(α) a prvek Tr_{F}(α) nazýváme absolutní stopa α ∈ F.

Lemma 4.1. Platí Tr_{F/K} (α) ∈ K pro libovolné α ∈ F.

Důkaz. Nechť f(x) = x^{d} + a_{d−1}x^{d−1} + … + a_{1}x + a_{0} ∈ K[x] je minimální polynom prvku α ∈ F nad K. Protože f(x)|x^{q^{m}} − x, platí d|m. Polynom f(x)^{\frac{m}{d}} = g(x) se nazývá charakteristický polynom α nad K. Kořeny f(x) jsou α, α^{q}, α^{q^{2}}, … α^{q^{d−1}} a všechny prvky konjugované k α nad K jsou právě všechny prvky kořeny polynomu g(x) = x^{m} + b_{m−1}x^{m−1} + … + b_{1}x + b_{0} = (x − α)(x − α^{q})(x − α^{q^{2}}) … (x − α^{q^{m−1}}). Roznásobením pravé strany dostáváme

x^{m} + b_{m−1}x^{m−1} + … + b_{1}x + b_{0} = x^{m} + (−α − α^{q} − … − α^{q−1}) · x^{m−1} + …

Tedy Tr_{F/K} (α) = −b_{m−1} ∈ K. □

Poznámka. Tedy platí Tr_{F/K} : F → K.

Věta 4.2 (O stopě). Nechť F = F_{q^{m}} a K = F_{q}. Potom Tr_{F/K} má následující vlastnosti

(1) Tr_{F/K} (α + β) = Tr_{F/K} (α) + Tr_{F/K} (β) pro všechny α, β ∈ F

(2) Tr_{F/K} (c · α) = c · Tr_{F/K} (α) pro všechna c ∈ K a α ∈ F

(3) Tr_{F/K} : F → K je lineární zobrazení na celé těleso K

(4) Tr_{F/K} (a) = m · a pro všechna a ∈ K

(5) Tr_{F/K} (α^{q}) = Tr_{F/K} (α) pro všechna α ∈ F

Důkaz. (1) Platí Tr_{F/K} (α + β) = (α + β) + (α + β)^{q} + (α + β)^{q^{2}} + … + (α + β)^{q^{m−1}} = α + β + α^{q} + β^{q} + α^{q^{2}} + β^{q^{2}} + … + α^{q^{m−1}} + β^{q^{m−1}} = Tr_{F/K} (α) + Tr_{F/K} (β).

(2) Platí Tr_{F/K} (c · α) = c · α + (c · α)^{q} + … + (c · α)^{q^{m−1}} = c · α + c · α^{q} + c · α^{q^{2}} + … + c · α^{q^{m−1}} = c · Tr_{F/K} (α), protože c ∈ K = F_{q}.

(3) Lineárnost zobrazení plyne z předchozích dvou bodů. Stačí tedy najít α ∈ F, pro které 0 ≠ Tr_{F/K} (α) = α + α^{q} + … + α^{q^{m−1}}. Je-li Tr_{F/K} (α) = 0, je α kořen rovnice x + x^{q} + … + x^{q^{m−1}} ∈ K[x]. Takových je nejvýše q^{m−1} < q^{m}.

(4) Pro a ∈ K platí Tr_{F/K} (a) = a + a^{q} + a^{q^{2}} + … + a^{q^{m−1}} = \underbrace{a + a + … + a}_{m-krát} =

m · a

(5) Platí Tr_{F/K} (α^{q}) = α^{q} + (α^{q})^{q} + … + (α^{q})^{q^{m−2}} + (α^{q})^{q^{m−1}} = α^{q} + α^{q^{2}} +

… + α^{q^{m−1}} + α = Tr_{F/K} (α)

□

Věta 4.3. Nechť F = F_{q^{m}} ⊇ F_{q} = K. Pak všechna lineární zobrazení z F do K jsou tvaru L_{β}(α) = Tr_{F/K} (α · β) pro β ∈ F.

Je-li β ≠ γ, pak L_{β} ≠ L_{γ}.

Důkaz. Nejprve dokážeme, že L_{β}(α) je lineární zobrazení. Platí L_{β}(α_{1} + α_{2}) = Tr_{F/K} ((α_{1} + α_{2})β) = Tr_{F/K} (α_{1}β) + Tr_{F/K} (α_{2}β) = L_{β}(α_{1}) + L_{β}(α_{2}) pro všechny α_{1}, α_{2} ∈ F. Podobně L_{β}(cα) = Tr_{F/K} (cαβ) = c · Tr_{F/K} (αβ) = c · L_{β}(α).

Je-li β ≠ γ, potom existuje prvek α ∈ F takový, že Tr_{F/K} ((β − γ)α) ≠ 0 a tedy L_{β}(α) ≠ L_{γ}(α). Počet lineárních zobrazení z F do K je q^{m}, tedy stejný jako počet zobrazení L_{β}. □

Věta 4.4. Nechť F = F_{q^{m}} ⊇ F_{q} = K. Potom pro α ∈ F platí Tr_{F/K} (α) = 0 právě tehdy, když α = β^{q} − β pro nějaké β ∈ F.

Důkaz. (⇐) Plyne z Věty 4.2 (5), protože Tr_{F/K} (α) = Tr_{F/K} (β^{q}−β) = Tr_{F/K} (β^{q})− Tr_{F/K} (β) = Tr_{F/K} (β) − Tr_{F/K} (β) = 0.

(⇒) Nechť Tr_{F/K} (α) = 0. Vezmeme polynom x^{q} − x − α ∈ F[x]. Buď β kořen polynomu x^{q} −x−α v nějakém rozšíření E ⊇ F. Platí β^{q} −β = α. Zbývá dokázat, že β ∈ F_{q^{m}}. Platí 0 = Tr_{F/K} (α) = α+α^{q}+α^{q^{2}} +…+α^{q^{m−1}} = β^{q}−β+(β^{q}−β)^{q}+(β^{q}− β)^{q^{2}} +…+(β^{q} −β)^{q^{m−1}} = (β^{q} −β)+(β^{q^{2}} −β^{q})+(β^{q^{3}} −β^{q^{2}})+…+(β^{q^{m}} −β^{q^{m−1}}) = β^{q^{m}} − β. Tedy β^{q^{m}} − β = 0 a proto β ∈ F_{q^{m}}. □

Věta 4.5 (O tranzitivitě stopy). Jsou-li K = F_{q} ⊆ F = F_{q^{m}} ⊆ E = F_{q^{m.n}} konečná tělesa, pak Tr_{E/K} = Tr_{F/K} ∘ Tr_{E/F} .

Důkaz. Je-li α ∈ E, pak

Tr_{F/K} (Tr_{E/F} (α)) = ∑_{i=0}^{m−1}(Tr_{E/F} (α))^{q^{i}} = ∑_{i=0}^{m−1}(∑_{j=0}^{n−1}(α^{q^{m}})^{j})^{q^{i}}

a dále

∑_{i=0}^{m−1}(∑_{j=0}^{n−1}(α^{q^{m}})^{j})^{q^{i}} ∑_{i=0}^{m−1} ∑_{j=0}^{n−1} α^{q^{mj+i}} = ∑_{k=0}^{mn−1} α^{q^{k}} = Tr_{E/K} (α).

□

Definice. Nechť F = F_{q^{m}} ⊇ F_{q} = K. Pak prvek

N_{F/K} (α) = α · α^{q} · α^{q^{2}} · . . . · α^{q^{m−1}} = α^{\frac{q^{m}−1}{q−1}}

nazýváme norma α ∈ F nad K.

Poznámka. Pro všechna α ∈ F je N_{F/K} (α) ∈ K, neboť je až na znaménko rovna absolutnímu členu charakteristického polynomu prvku α nad K - viz důkaz Lemma 4.1.

Věta 4.6 (O normě). Pro funkci N_{F/K} platí (1) N_{F/K} (α · β) = N_{F/K} (α) · N_{F/K} (β) pro všechna α, β ∈ F

(2) N_{F/K} je zobrazení z F na K a z F^{∗} na K^{∗}
(3) N_{F/K} (d) = d^{m} pro všechna d ∈ K
(4) N_{F/K} (α^{q}) = N_{F/K} (α) pro všechna α ∈ F

Důkaz. (1) Platí N_{F/K} (α · β) = (α · β) · (α · β)^{q} · . . . · (α · β)^{q^{m−1}} = α · α^{q} · . . . ·

α^{q^{m−1}} · β · β^{q} · . . . · β^{q^{m−1}} = N_{F/K} (α) · N_{F/K} (β)

(2) Podle (1) je N_{F/K} : F^{∗} → K^{∗} homomorfismus grup. V jádru N_{F/K} jsou

kořeny rovnice

x^{\frac{q^{m}−1}{q−1}} − 1 ∈ K[x]

Buď d počet prvků (řád) jádra N_{F/K} . Platí d ≤ (q^{m} − 1)/(q − 1) a současně d|(q^{m} − 1). Tedy Im (N_{F/K} ) má velikost (q^{m} − 1)/d ≥ q − 1, což je řád K^{∗}.

(3) Platí N_{F/K} (d) = d · d^{q} · d^{q^{2}} · . . . · d^{q^{m−1}} = \underbrace{d · d · . . . · d}_{m-krát} = d^{m}

(4) Platí N_{F/K} (α^{q}) = α^{q}·(α^{q})^{q}·· · ··(α^{q})^{q^{m−2}} ·(α^{q})^{q^{m−1}} = α^{q}·α^{q^{2}} ·. . .·α^{q^{m−1}} ·α =

N_{F/K} (α)

□

Věta 4.7 (O tranzitivitě normy). Jsou-li K = F_{q} ⊆ F = F_{q^{m}} ⊆ E = F_{q^{m.n}} konečná tělesa, pak pro libovolné α ∈ E platí N_{E/K} (α) = N_{F/K} (N_{E/F} (α)).

Důkaz. Z definice platí N_{E/F} (α) = α^{\frac{(q^{m})^{n}−1}{q^{m}−1}} . Pak platí

N_{F/K} (N_{E/F} (α)) = (N_{E/F} (α))^{\frac{q^{m}−1}{q−1}} = (α^{\frac{(q^{m})^{n}−1}{q^{m}−1}} )^{\frac{q^{m}−1}{q−1}} = α^{\frac{q^{m.n}−1}{q−1}} = N_{E/K} (α).

□

Je-li α_{1}, …, α_{m} báze F = F_{q^{m}} nad K = F_{q}, potom libovolný prvek α ∈ F_{q^{m}} můžeme vyjádřit jednoznačně ve tvaru

α = c_{1}(α) · α_{1} + c_{2}(α) · α_{2} + … + c_{m}(α) · α_{m}

kde c_{i}(α) ∈ F_{q} pro i = 1, …, m.

Každé zobrazení c_{i}(α) : F_{q^{m}} → F_{q} je lineární funkcionál. Pro každé i = 1, …, m existuje β_{i} ∈ F_{q^{m}} takové, že

c_{i}(α) = Tr_{F/K} (αβ_{i})

Je-li α = α_{j}, pak

c_{i}(α_{j}) = δ_{ij} = \{ \begin{matrix}0, & i ≠ j \\ 1, & i = j. \end{matrix}

Tedy Tr_{F/K} (α_{j}β_{i}) = δ_{ij}.

Posloupnost β_{1}, …, β_{m} je lineárně nezávislá nad F_{q}, neboť z rovnosti

d_{1}β_{1} + … + d_{m}β_{m} = 0

pro d_{1}, …, d_{m} ∈ F_{q} plyne pro každé j = 1, …, m

d_{1}β_{1}α_{j} + … + d_{m}β_{m}α_{j} = 0,
Tr_{F/K} (d_{1}β_{1}α_{j} + … + d_{m}β_{m}α_{j}) = 0,
d_{1}Tr_{F/K} (β_{1}α_{j}) + … + d_{m}Tr_{F/K} (β_{m}α_{j}) = 0
d_{j} · 1 = 0.

Proto β_{1}, …, β_{m} je opět báze F_{q^{m}} nad F_{q}.

Definice. Báze β_{1} …, β_{m} se nazývá duální báze k bázi α_{1}, …, α_{m} v F_{q^{m}} nad F_{q}.

Poznámka. Duální báze k bázi α_{1}, …, α_{m} je určena jednoznačně bází α_{1}, …, α_{m}. To plyne ze vztahu c_{i}(α) = Tr_{F/K} (αβ_{i}). Proto duální báze k bázi β_{1}, …, β_{m} je původní báze α_{1}, …, α_{m}.

Příklad. Nechť F_{8} ⊇ F_{2} je kořenové rozšíření F_{2} určené polynomem f(x) = x^{3} + x^{2} + 1 ∈ F_{2}[x]. Buď α ∈ F_{8} kořen f(x). Uvažujme prvky α, α^{2}, α^{3} = α^{2} + 1, α^{4} = α(α^{2}+1) = α^{3}+α = α^{2}+α+1, α^{5} = α(α^{2}+α+1) = α^{3}+α^{2}+α = α^{2}+1+α^{2}+α = α + 1, α^{6} = α(α + 1) = α^{2} + α, α^{7} = 1.

Prvky α, α^{2}, α^{4} tvoří bázi F_{8} nad F_{2}. Ukážeme, že β_{1} = α, β_{2} = α^{2}, β_{3} = α^{2} + α + 1 je duální báze k α, α^{2}, α^{2} + α + 1. Plyne to z následujících rovností.

Tr(α_{1}β_{1}) = Tr(αα) = Tr(α^{2}) = α^{2} + α^{4} + α^{8} = α^{2} + α^{2} + α + 1 + α = 1.

Tr(α_{1}β_{2}) = Tr(αα^{2}) = Tr(α^{3}) = α^{3} + α^{6} + α^{12} = α^{2} + 1 + α^{2} + α + α + 1 = 0.

Analogicky dál.

Definice. Báze F_{q^{m}} nad F_{q} tvaru α, α^{q}, α^{q^{2}} …, α^{q^{m−1}} pro nějaké α ∈ F_{q^{m}} se nazývá normální báze F_{q^{m}} nad F_{q}.

Věta 4.8. Je-li F_{q^{m}}rozšíření F_{q}, pak existuje v F_{q^{m}} nad F_{q} normální báze. Dokonce existuje normální báze tvořená primitivními prvky F_{q^{m}}.

Definice. Nechť F = F_{q^{m}} ⊇ F_{q} = K a α_{1}, …, α_{m} ∈ F. Označme

B = (Tr_{F/K} (α_{i}, α_{j}))_{i,j}

Čili B je čtvercová matice řádu m, která má na místě (i, j) prvek Tr_{F/K} (α_{i}, α_{j}). Pak Δ_{F/K} (α_{1}, …, α_{m}) = detB se nazývá diskriminant α_{1}, …, α_{m} nad F_{q}.

Věta 4.9. Prvky α_{1}, …, α_{m} ∈ F tvoří bázi F = F_{q^{m}} nad K = F_{q} právě tehdy, když Δ_{F/K} (α_{1}, …, α_{m}) ≠ 0.

Důkaz. (⇒) Nechť α_{1}, …, α_{m} je báze F nad K. Ukážeme, že řádky matice B jsou lineárně nezávislé. Je-li d_{1}·Tr_{F/K} (α_{1}α_{j})+d_{2}·Tr_{F/K} (α_{2}α_{j})+…+d_{m}·Tr_{F/K} (α_{m}α_{j}) = 0 pro nějaké d_{1}, …, d_{m} ∈ K a každé j = 1, …, m, pak platí

Tr_{F/K} ((d_{1}α_{1} + … + d_{m}α_{m}) · α_{j}) = 0

pro j = 1, …, m. Označme si β = d_{1}α_{1} + … + d_{m}α_{m}. Tedy Tr_{F/K} (βα_{j}) = 0 pro j = 1, …, m. Protože α_{1}, …, α_{m} je báze F nad K, plyne odtud Tr_{F/K} (βα) = 0 pro libovolné α ∈ F_{q^{m}}. Proto β = 0, neboli d_{1}α_{1} + … + d_{m}α_{m} = 0. Protože α_{1}, …, α_{m} je báze F nad K, platí d_{1} = d_{2} = … = d_{m} = 0.

(⇐) Nechť Δ_{F/K} (α_{1}, …, α_{m}) ≠ 0 a c_{1}α_{1}+…+c_{m}α_{m} = 0 pro nějaké c_{1}, …, c_{m} ∈ K. Pak platí c_{1}α_{1}α_{j} + … + c_{m}α_{m}α_{j} = 0 pro libovolné j = 1, …, m. Proto 0 = Tr_{F/K} (c_{1}α_{1}α_{j} + … + c_{m}α_{m}α_{j}) = c_{1} · Tr_{F/K} (α_{1}α_{j}) + … + c_{m} · Tr_{F/K} (α_{m}α_{j}) pro j = 1, …, m. Tedy lineární kombinace řádků matice B s koeficienty c_{1}, …, c_{m} se rovná 0. Protože detB = Δ_{F/K} (α_{1}, …, α_{m}) ≠ 0, jsou řádky matice B lineárně nezávislé a proto c_{1} = … = c_{m} = 0. Tedy α_{1}, …, α_{m} jsou lineárně nezávislé nad K a tvoří bázi F nad K. □

Označme si nyní

A = ( α_{1}  α_{2} … α_{m} ; α_{1}^{q}  α_{2}^{q} … α_{m}^{q} ; ⋮ ; α_{1}^{q^{m−1}} α_{2}^{q^{m−1}} … α_{m}^{q^{m−1}} ) = (α_{j}^{q^{i−1}} )_{i,j}

Platí Tr_{F/K} (α_{i}α_{j}) = α_{i}α_{j} + α_{i}^{q}α_{j}^{q} + … + α_{i}^{q^{m−1}} α_{j}^{q^{m−1}} . Proto platí A^{T} · A = B a tedy detB = (detA)^{2}.

Důsledek 4.10. Prvky α_{1}, …, α_{m} tvoří bázi F nad K právě tehdy, když detA ≠ 0.

5. Odmocniny z 1 a cyklotomické polynomy

Definice. Je-li K libovolné těleso, pak rozkladové rozšíření K určené polynomem x^{n}−1 ∈ K[x] se nazývá n-té cyklotomické těleso nad K a označuje se K^{(n)}. Množina všech kořenů polynomu x^{n} − 1 v K^{(n)} se označuje E^{(n)}.

Věta 5.1. Nechť n > 0 a K je těleso charakteristiky p. Pak platí

(1) pokud p ∤ n, pak E^{(n)} je cyklická podgrupa řádu n multiplikativní grupy (K^{(n)})^{∗} tělesa K^{(n)},

(2) pokud p|n a n = p^{l}m, kde p ∤ m, pak K^{(n)} se rovná K^{(m)} a kořeny polynomu x^{n} − 1 jsou prvky E^{(m)}, každý s násobností p^{l}.

Důkaz. (1) Platí, že x^{n} − 1 a nx^{n} − 1 nemají společný kořen v K[n], tedy jsou v K[x] nesoudělné a x^{n} − 1 nemá žádný vícenásobný kořen. Tedy E^{(n)} obsahuje přesně n prvků.

Jsou-li ξ, μ ∈ E^{(n)}, pak (ξμ)^{n} = ξ^{n}μ^{n} = 1. Protože ξ je kořen x^{n} − 1, platí ξ^{n} = 1. Proto (ξ^{−1})^{n} = 1.(ξ^{−1})^{n} = ξ^{n}.(ξ^{−1})^{n} = 1^{n} = 1. Tedy E^{(n)} je podgrupa (K^{(n)})^{∗}.

Nechť n = p_{1}^{l_{1}} · . . . · p_{t}^{l_{t}} rozklad na prvočinitele. Pak pro každé i = 0, …, t

existuje prvek a_{i} ∈ E^{(n)}, pro který platí ai^{\frac{n}{p_{i}}} ≠ 1. Potom prvek b_{i} = ai^{\frac{n}{p{l_{i} \atop i}}} má řád p_{i}^{l_{i}} a b_{1}, …, b_{t} je generátor grupy E^{(n)}.

(2) Platí x^{n} − 1 = (x^{m} − 1)^{p^{l}} v K[x], odkud už tvrzení snadno plyne.
□

Definice. Nechť K je těleso charakteristiky p a nechť p ∤ n. Pak libovolný generátor E^{(n)} nazýváme primitivní n-tá odmocnina z 1indexprimitivní n-tá odmocnina z 1 nad K.

Poznámka. Je-li ξ generátor E^{(n)}, pak E^{(n)} = {1, ξ, ξ^{2}, …, ξ^{n−1}}. Platí, že ξ^{s} je také generátor E^{(n)} právě tehdy, když NSD(s, n) = 1. Tedy pokud p = char T nedělí n, pak existuje φ(n) primitivních n-tých odmocnin z 1 nad K.

Definice. Nechť K je těleso charakteristiky p, p ∤ n a ξ je primitivní n-tá odmocnina z 1. Pak polynom

Q_{n}(x) = ∏_{\begin{matrix}0≤s<n \\ NSD (s,n)=1 \end{matrix}} (x − ξ^{s})

se nazývá n-tý cyklotomický polynom nad K.

Poznámka. Polynom Q_{n}(x) je nezávislý na výběru ξ, stupeň Q_{n}(x) je φ(n) a koeficienty leží v K^{(n)}.

Věta 5.2. Nechť K je těleso charakteristiky p, n > 0 je celé číslo nesoudělné s p. Pak platí

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

(2) koeficienty Q_{n}(x) leží v prvotělese tělesa K. Je-li p = 0, pak koeficienty

Q_{n}(x) jsou celá čísla. V K^{(n)} platí x^{n} − 1 = ∏_{ξ∈E^{(n)}} (x − ξ)

Důkaz. (1) Libovolný prvek ξ ∈ E^{(n)} je primitivní d-tá odmocnina z 1 pro nějaké d|n. Je tomu tak proto, že každý prvek ξ ∈ E^{(n)} má řád d pro nějaké d|n, platí tedy ξ^{d} − 1 = 0. Tedy ξ je d-tá odmocnina z 1 a je primitivní. Takže platí x − ξ dělí Q_{d}(x) a proto x^{n} − 1 = ∏_{d|n} Q_{d}(x).

(2) Budeme postupovat indukcí dle n. Platí,že Q_{1}(x) = x − 1 má koeficienty v prvotělese tělesa K. Nechť tvrzení platí pro všechna d < n. Pak z rovnosti x^{n} − 1 = ∏_{d|n} Q_{d}(x) spočteme

Q_{n}(x) = \frac{x^{n} − 1}{∏\begin{matrix}d|n \\ d<n \end{matrix} Q_{d}(x)}

Čitatel i jmenovatel zlomku mají koeficienty v prvotělese tělesa K. Pomocí dělení polynomů se zbytkem dostaneme, že i Q_{n}(x) má koeficienty v prvotělese tělesa K.

V případě p = 0 jsou koeficienty Q_{1}(x) celočíselné. Indukční předpoklad je, že koeficienty Q_{d}(x) jsou celočíselné pro každé d < n. Z rovnosti

Q_{n}(x) = \frac{x^{n} − 1}{∏\begin{matrix}d|n \\ d<n \end{matrix} Q_{d}(x)}

pak vyplývá pomocí indukčního předpokladu, že také koeficienty Q_{n}(x) celočíselné, neboť každý polynom Q_{d}(x) pro d < n je monický a v procesu dělení se zbytkem jsou všechny koeficienty stále celočíselné.

□

Poznámka. Ve Věte 5.2 (1), je-li char K = 0, pak je to rozklad na ireducibilní činitele, tj. všechny polynomy Q_{d}(x) jsou ireducibilní nad K. V tělese nenulové charakteristiky to tak být nemusí.

Příklad. Spočtěte Q_{r}(x) pro r prvočíslo.

Podle Věty 5.2 (1) dostáváme x^{r} − 1 = Q_{1}(x) · Q_{r}(x). Víme, že Q_{1}(x) = x − 1. Tedy

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

Příklad. Spočtěte Q_{r^{k}}(x) pro r prvočíslo a k nezáporné celé číslo.

Protože r je prvočíslo, všechny dělitele r^{k} jsou r^{0} = 1, r^{1} = r, r^{2}, r^{3}, …, r^{k−1}, r^{k}. Podle Věty 5.2 (1) tedy platí

x^{r^{k}} − 1 = Q_{1}(x) · Q_{r}(x) · Q_{r^{2}}(x) · . . . · Q_{r^{k−1}}(x) · Q_{r^{k}}(x)

Všimněme si, že platí x^{r^{k−1}} − 1 = Q_{1}(x) · Q_{r}(x) · Q_{r^{2}}(x) · . . . · Q_{r^{k−1}}(x). Tedy

Q_{r^{k}}(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

Věta 5.3. n-té cyklotomické rozšíření tělesa K je jednoduchým algebraickým rozšířením tělesa K určeným vhodným ireducibilním polynomem z K[x].

Nechť K = F_{q} a NSD(q, n) = 1. Potom se Q_{n}(x) rozkládá na součin \frac{φ(n)}{d} různých monických ireducibilních polynomů téhož stupně d, K^{(n)} je rozkladové rozšíření tělesa K určené libovolným ireducibilním faktorem Q_{n} v K[x] a dim_{K} K^{(n)} = d, kde d je nejmenší kladné přirozené číslo takové, že q^{d} ≡ 1 mod n.

Důkaz. Pokud char K ∤ n, vezměme primitivní n-tou odmocninu z 1 a označme ji ξ. Nejmenší podtěleso K^{(n)} obsahující K a ξ musí obsahovat všechny prvky {1, ξ, ξ^{2} …, ξ^{n−1}}. Ty jsou navzájem různé a tvoří všechny kořeny polynomu x^{n}−1.

Tedy polynom x^{n} − 1 se rozkládá na součin lineárních činitelů nad nejmenším podtělesem tělesa K^{(n)} obsahujícím K a ξ. Protože K^{(n)} je rozkladové rozšíření K určené polynomem x^{n} − 1, platí, že K^{(n)} je nejmenší podtěleso K^{(n)} obsahující K a ξ. Vezměme minimální polynom prvku ξ nad K a označme jej f. Potom K^{(n)} je kořenovým rozšířením K určeným f.

Pokud p = char K | n, vezmeme rozklad n = m · p^{l}, kde p ∤ m. Pak K^{(n)} = K^{(m)}, char K ∤ m a K^{(m)} je jednoduché algebraické rozšíření K určené vhodným polynomem podle předchozího odstavce.

Zbývá dokázat druhou část věty. Nechť K = F_{q} a NSD(q, n) = 1. Buď ξ primitivní n-tá odmocnina z 1. Prvek ξ leží v tělese F_{q^{k}} právě tehdy, když platí ξ^{q^{k}−1} = 1, což je ekvivalentní n|q^{k} − 1, tedy q^{k} ≡ 1 mod n. Nechť d je nejmenší k > 0, pro které to platí. Pak platí ξ ∈ F_{q^{d}} a neleží v žádném vlastním podtělese F_{q^{d}}. Tedy minimální polynom ξ nad F_{q} má stupeň d. Minimální polynom ξ nad F_{q} je ireducibilní nad F_{q}. Protože to platí pro libovolnou primitivní n-tou odmocninu z 1 nad F_{q}, rozkládá se Q_{n}(x) na součin ireducibilních polynomů stupně d a těch je \frac{φ(n)}{d}. □

Příklad. Buď K = F_{11}. Spočtěte Q_{12}(x). Dále spočtěte nejmenší d, pro které platí 11^{d} ≡ 1 mod 12.

Podle Věty 5.2 platí

x^{12} − 1 = Q_{1}(x) · Q_{2}(x) · Q_{3}(x) · Q_{6}(x) · Q_{4}(x) · Q_{12}(x)

Z Věty 5.2 taktéž víme, že Q_{1}(x)·Q_{2}(x)·Q_{3}(x)·Q_{6}(x) = x^{6} −1 a Q_{4} = x^{2} +1. Tedy x^{12} − 1 = Q_{1}(x) · Q_{2}(x) · Q_{3}(x) · Q_{6}(x) · Q_{4}(x) · Q_{12}(x) = (x^{6} − 1)(x^{2} + 1) · Q_{12}(x) = (x^{8} + x^{6} − x^{2} − 1) · Q_{12}(x) a proto

Q_{12}(x) = \frac{x^{12} − 1}{x^{8} + x^{6} − x^{2} − 1} = x^{4} − x^{2} + 1

Hledané d spočteme podle Věty 5.3. Platí NSD(11, 12) = 1 a podle Věty 5.3 se Q_{12}(x) rozkládá na součin \frac{φ(12)}{d} různých monických polynomů téhož stupně d. Platí Q_{12}(x) = x^{4} − x^{2} + 1 = (x^{2} + 5x + 1)(x^{2} − 5x + 1). Jelikož Q_{12}(x) se rozkládá na 2 polynomy stupně 2, je d = 2. Platí taky d = \frac{φ(12)}{2} = \frac{4}{2} = 2. Tedy F_{11}^{(12)} = F_{11^{2}} .

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 považovat 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}.

KONEČNÁ TĚLESA 23

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^{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í.

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.

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 vlastnosti, ž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 úpravě straně poslední rovnosti (každý z nich má stupeň aspoň 1) nemůže být větší než počet různých ireducibilní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

8. Výpočet kořenů polynomů nad konečnými tělesy

Buď f(x) ∈ F_{q}[x]. Při hledání kořenů polynomu f, které leží v F_{q}, napřed izolujeme tu část polynomu f(x), která obsahuje lineární dělitele. To uděláme snadno, neboť víme, že každý prvek a ∈ F_{q} je kořenem polynomu x^{q} − x ∈ F_{q}[x]. Každý lineární dělitel polynomu f(x) tak dělí také polynom x^{q} − x a tedy také NSD(f(x), x^{q} − x). Tento největší společný dělitel je tak součinem všech lineárních dělitelů polynomu f(x).

Můžeme tedy od začátku předpokládat, že polynom f(x) ∈ F_{q}[x], jehož kořeny chceme najít, se nad F_{q} rozkládá na součin lineárních činitelů.

Budeme se zabývat pouze případem, kdy q se rovná nějakému prvočíslu p. Předpokládáme, že

f(x) = ∏_{i=1}^{n}(x − c_{i}),

kde c_{1}, …, c_{n} jsou navzájem různé prvky F_{p}. Je-li p malé číslo, pak lze najít kořeny f(x) zkusmo dosazováním, neboli výpočtem hodnot f(0), f(1), …, f(p − 1).

Pro velké p > 2 použijeme následující metodu. Pro b ∈ F_{p} platí

f(x − b) = ∏_{i=1}^{n}(x − (b + c_{i}))|x^{p} − x = x(x^{(p−1)/2} + 1)(x^{(p−1)/2} + 1).

Pokud je x dělitelem f(x − b), platí f(−b) = 0 a našli jsme kořen f(x).

Pokud x není dělitelem f(x − b), platí f(x)|(x^{(p−1)/2} + 1)(x^{(p−1)/2} + 1) a tedy

f(x − b) = NSD(f(x − b), x^{(p−1)/2} + 1) · NSD(f(x), x^{(p−1)/2} − 1)

Dělí-li f(x − b) jednoho z činitelů na pravé straně, pak platí buď x^{(p−1)/2} ≡ 1 mod f(x − b) nebo x^{(p−1)/2} ≡ −1 mod f(x − b). Pokud

x^{(p−1)/2} ≢ ±1 mod f(x − b)

pak rovnost f(x − b) = NSD(f(x − b), x^{(p−1)/2} + 1) · NSD(f(x), x^{(p−1)/2} − 1) dává netriviální rozklad f(x − b). Dosadíme-li x + b za x, dostaneme netriviální rozklad f(x). V málo pravděpodobném případě, že x^{(p−1)/2} ≡ ±1 mod f(x − b) prostě zkusíme jiné b ∈ F_{p}. Tím dostáváme pravděpodobnostní algoritmus pro nalezení kořenů f(x) ∈ F_{p}[x]. To, jak funguje, si ukážeme v následujícím příkladu.

Příklad. Najděte ty kořeny polynomu f(x) = x^{6} − 7x^{5} + 3x^{4} − 7x^{3} + 4x^{2} − x − 2 ∈ F_{17}, které leží v F_{17}. \underline{Řešení:} Hledané kořeny polynomu f(x) jsou právě kořeny polynomu g(x) = NSD(f(x), x^{17}− x). Eukleidovým algoritmem zjistíme, že g(x) = x^{4} +6x^{3} −5x^{2} +7x−2. Při hledání kořenů g(x) budeme postupovat způsobem uvedený před příkladem.

Napřed zvolíme b = 0. Přímým výpočtem zjistíme, že

x^{(p−1)/2} = x^{8} ≡ 1 mod g(x)

takže tato volba b nedává netriviální rozklad g(x). Zvolíme tedy b = 1. Pak g(x −

1) = x^{4} + 2x^{3} − 3x − 2 a x^{(p−1)/2} = x^{8} ≡ −4x^{3} − 7x^{2} + 8x − 5 mod g(x − 1), takže volba b = 1 nám dává netriviální faktorizaci g(x − 1). Platí

NSD(g(x − 1), x^{8} + 1) = NSD(x^{4} + 2x^{3} − 3x − 2, −4x^{3} − 7x^{2} + 8x − 4) = x^{2} − 7x + 4

a

NSD(g(x − 1), x^{8} − 1) = NSD(x^{4} + 2x^{3} − 3x − 2, −4x^{3} − 7x^{2} + 8x − 6) = x^{2} − 8x + 8 a tedy g(x − 1) = (x^{2} − 7x + 4)(x^{2} − 8x + 8), což vede k částečné faktorizaci

g(x) = (x^{2} − 5x − 2)(x^{2} − 6x + 1) = g_{1}(x)g_{2}(x)

Abychom rozložili g_{1}(x) a g_{2}(x), zkusíme b = 2. Platí g_{1}(x − 2) = x^{2} + 8x − 5 a x^{8} ≡ −8x + 2 mod g_{1}(x − 2). Spočítáme

NSD(g_{1}(x − 2, x^{8} + 1)) = NSD(x^{2} + 8x − 5, −8x + 3) = x + 6

a tedy g_{1}(x − 2) = (x + 6)(x + 2), a také g_{1}(x) = (x + 8)(x + 4).

Pokud jde o g_{2}(x), platí g_{2}(x − 2) = x^{2} + 7x = x(x + 7), čili −2 je kořen g_{2}(x) a g_{2}(x) = (x + 2)(x − 8). Zjistili jsme tak, že

g(x) = g_{1}(x)g_{2}(x) = (x + 8)(x + 4)(x + 2)(x − 8)

a kořeny g(x) a tedy i f(x) v F_{17} jsou −8, −4, −2, 8.

Pro hledání kořenů polynomů s koeficienty v konečných tělesech, která nemají prvočíselnou velikost, se používají jiné algoritmy.