Konečné těleso

Konečné těleso (též Galoisovo těleso na počest Évarista Galoise, obvykle značeno ${\displaystyle 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ů.

Vlastnosti

• Počet prvků konečného tělesa je roven ${\displaystyle p^{k}}$, kde ${\displaystyle p}$ je prvočíslo a ${\displaystyle k}$ je kladné přirozené číslo.
• Charakteristika tělesa ${\displaystyle GF(p^{k})}$ je rovna právě prvočíslu ${\displaystyle p}$.
• Konečná tělesa jsou komutativní (Wedderburnova věta).
• Konečná tělesa lze klasifikovat podle velikosti; platí totiž, že až na izomorfismus existuje vždy jen jediné konečné těleso o daném počtu prvků.
• Žádné konečné těleso není algebraicky uzavřené neboť označíme-li prvky konečného tělesa po řadě ${\displaystyle a_{1},a_{2},\dots ,a_{k}}$, můžeme zkonstruovat mnohočlen${\displaystyle (x-a_{1})(x-a_{2})\cdots (x-a_{k})+1}$, který je zřejmě stupně alespoň 1 a přitom žádný z ${\displaystyle a_{1},a_{2},\dots ,a_{k}}$ není jeho kořenem.

Reprezentace

${\displaystyle GF(p)}$ jsou celá čísla modulo dané prvočíslo ${\displaystyle p}$ neboli ${\displaystyle Z_{p}}$. Typická reprezentace Galoisova tělesa ${\displaystyle GF(p^{k})}$ jsou polynomy nad ${\displaystyle Z_{p}}$ modulo definiční polynom stupně ${\displaystyle 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í

Konečná tělesa jsou důležitým nástrojem mimo jiné teorie čísel, algebraické geometrie a kryptografie.

Využití v kódování

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

Externí odkazy

• Obrázky, zvuky či videa k tématu konečné těleso na Wikimedia Commons