Konečné těleso

Konečné těleso (též Galoisovo těleso na počest Évarista Galoise, obvykle značeno $GF(p^k)$) je v matematice, přesněji v abstraktní algebře, označení pro takové těleso, které má konečný počet prvků.

Konečná tělesa jsou důležitým nástrojem mimo jiné teorie čísel, algebraické geometrie a kryptografie. Lze je klasifikovat podle velikosti; platí totiž, že až na izomorfismus existuje vždy jen jediné konečné těleso o $p^k$ prvcích, kde $p$ je prvočíslo a $k$ je kladné přirozené číslo. Charakteristika daného tělesa je přitom rovna právě prvočíslu $p$.

Reprezentace

$GF(p^1)$ jsou celá čísla modulo dané prvočíslo $p$ neboli $Z_p$ (modulo složené číslo není těleso, protože násobků dělitelů modula je více a žádný z nich nemá multiplikativní inverzní prvek). Typická reprezentace Galoisova tělesa $GF(p^k)$ jsou polynomy nad $Z_p$ modulo definiční polynom stupně $k$. Těleso tímto způsobem dostaneme právě když je definiční polynom ireducibilní.

Ne vždy je x primitivním prvkem tělesa (generátorem multiplikativní grupy). Například pro GF(3²) při definičním polynomu x²+1 generuje pouze polovinu prvků a jako generátor je potřeba vzít x+1. Při definičním polynomu x²+x-1 ale x stačí.

Využití v kódování

V kódování jsou nejčastěji používána $GF(2^{2^k})$. V takovém případě je používán izomorfismus mezi číslem dle jeho $2^k$ bitového zápisu na polynomy nad bity tak, že bit řádu $\ell$ určuje koeficient u $x^\ell$. Pozor, ač jsou při různé volbě definičního polynomu odpovídající tělesa isomorfní, kódování dává různé výsledky v závislosti na volbě definičního polynomu. Při výpočtech nad $GF(2^{2^k})$ sčítání odpovídá bitový xor. Pro násobení je nejjednodušší vytvořit si tabulky logaritmů a exponentů primitivního prvku tělesa $\alpha=x$ resp. v číselném pohledu $\alpha=2$. Tabulky logaritmů vytváříme na základě tabulky exponentů. Tabulku exponentů vyplňujeme postupně. Je-li $y$ reprezentace $\alpha^\ell$, pak reprezentaci $\alpha^{\ell+1}$ dostaneme buď jako $2y$, pokud je $2y<2^{2^k}$ nebo pomocí xor s číslem odpovídajícím definičnímu polynomu (pokud $2y\ge2^{2^k}$). Máme-li jak tabulky logaritmů, tak tabulky mocnin primitivního prvku, můžeme násobení počítat (pro nenulové činitele $a,b$) pomocí $\alpha^{\log a+\log b}$. Je-li jakýkoli činitel nulový, je samozřejmě i součin nulový.

Vlastnosti

• Žádné konečné těleso není algebraicky uzavřené neboť označíme-li prvky konečného tělesa po řadě $a_1,a_2,\dots,a_k$, můžeme zkonstruovat mnohočlen $(x-a_1)(x-a_2)\cdots(x-a_k) + 1$, který je zřejmě stupně alespoň 1 a přitom žádný z $a_1,a_2,\dots,a_k$ není jeho kořenem.