Multimediaexpo.cz je již 18 let na českém internetu !!
V tiskové zprávě k 18. narozeninám brzy najdete nové a zásadní informace.
Konečné těleso
Z Multimediaexpo.cz
Verze z 29. 9. 2021, 07:13
Konečné těleso (nebo Galoisovo těleso na počest Évarista Galoise (1811 – 1832), obvykle značeno <math>GF(p^k)</math>) je v matematice, přesněji v abstraktní algebře, označení pro takové těleso, které má konečný počet prvků.
Obsah |
Vlastnosti
- Počet prvků konečného tělesa je roven <math>p^k</math>, kde <math>p</math> je prvočíslo a <math>k</math> je kladné přirozené číslo.
- Charakteristika tělesa <math>GF(p^k)</math> je rovna právě prvočíslu <math>p</math>.
- 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ě <math>a_1,a_2,\dots,a_k</math>, můžeme zkonstruovat mnohočlen<math>(x-a_1)(x-a_2)\cdots(x-a_k) + 1</math>, který je zřejmě stupně alespoň 1 a přitom žádný z <math>a_1,a_2,\dots,a_k</math> není jeho kořenem.
Reprezentace
<math>GF(p)</math> jsou celá čísla modulo dané prvočíslo <math>p</math> neboli <math>Z_p</math>. Typická reprezentace Galoisova tělesa <math>GF(p^k)</math> jsou polynomy nad <math>Z_p</math> modulo definiční polynom stupně <math>k</math>. 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í
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 <math>GF(2^{2^k})</math>. V takovém případě je používán izomorfismus mezi číslem dle jeho <math>2^k</math> bitového zápisu na polynomy nad bity tak, že bit řádu <math>\ell</math> určuje koeficient u <math>x^\ell</math>. 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 <math>GF(2^{2^k})</math> sčítání odpovídá bitový xor. Pro násobení je nejjednodušší vytvořit si tabulky logaritmů a exponentů primitivního prvku tělesa <math>\alpha=x</math> resp. v číselném pohledu <math>\alpha=2</math>. Tabulky logaritmů vytváříme na základě tabulky exponentů. Tabulku exponentů vyplňujeme postupně. Je-li <math>y</math> reprezentace <math>\alpha^\ell</math>, pak reprezentaci <math>\alpha^{\ell+1}</math> dostaneme buď jako <math>2y</math>, pokud je <math>2y<2^{2^k}</math> nebo pomocí xor s číslem odpovídajícím definičnímu polynomu (pokud <math>2y\ge2^{2^k}</math>). Máme-li jak tabulky logaritmů, tak tabulky mocnin primitivního prvku, můžeme násobení počítat (pro nenulové činitele <math>a,b</math>) pomocí <math>\alpha^{\log a+\log b}</math>. Je-li jakýkoli činitel nulový, je samozřejmě i součin nulový.
Externí odkazy
|
| Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010 |
|---|
| Informace o článku.
Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. |