Konečné těleso

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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(32) při definičním polynomu x2+1 generuje pouze polovinu prvků a jako generátor je potřeba vzít x+1. Při definičním polynomu x2+x-1 ale x stačí.

Využití v kódování[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  • Žá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.