Konečné těleso

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)

Aktuální verze z 14. 8. 2022, 14:52

Konečné těleso (nebo Galoisovo těleso na počest Évarista Galoise (1811 – 1832), 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ů.

Vlastnosti

Počet prvků konečného tělesa je roven \(p^k\), kde \(p\) je prvočíslo a \(k\) je kladné přirozené číslo.
Charakteristika tělesa \(GF(p^k)\) je rovna právě prvočíslu \(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ě \(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.

Reprezentace

\(GF(p)\) jsou celá čísla modulo dané prvočíslo \(p\) neboli \(Z_p\). 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í

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 \(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ý.

Externí odkazy

Commons nabízí fotografie, obrázky a videa k tématu
Konečné těleso

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. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii

@@ Řádka 1: / Řádka 1: @@
-'''Konečné těleso''' (nebo '''Galoisovo těleso''' na počest Évarista Galoise (1811 – 1832), obvykle značeno <big>\(GF(p^k)</math>) je v [[matematika|matematice]], přesněji v [[abstraktní algebra|abstraktní algebře]], označení pro takové [[Těleso (algebra)|těleso]], které má konečný počet prvků.
+'''Konečné těleso''' (nebo '''Galoisovo těleso''' na počest Évarista Galoise (1811 – 1832), obvykle značeno <big>\(GF(p^k)\)</big>) je v [[matematika|matematice]], přesněji v [[abstraktní algebra|abstraktní algebře]], označení pro takové [[Těleso (algebra)|těleso]], které má konečný počet prvků.
 == Vlastnosti ==
-* Počet prvků konečného tělesa je roven <big>\(p^k</math>, kde <big>\(p</math> je [[prvočíslo]] a <big>\(k</math> je kladné [[přirozené číslo]].
+* Počet prvků konečného tělesa je roven <big>\(p^k\)</big>, kde <big>\(p\)</big> je [[prvočíslo]] a <big>\(k\)</big> je kladné [[přirozené číslo]].
-* [[Charakteristika (matematika)|Charakteristika]] tělesa <big>\(GF(p^k)</math> je rovna právě prvočíslu <big>\(p</math>.
+* [[Charakteristika (matematika)|Charakteristika]] tělesa <big>\(GF(p^k)\)</big> je rovna právě prvočíslu <big>\(p\)</big>.
 * Konečná tělesa jsou [[Komutativita|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é těleso|algebraicky uzavřené]] neboť označíme-li prvky konečného tělesa po řadě <big>\(a_1,a_2,\dots,a_k</math>, můžeme zkonstruovat mnohočlen<big>\((x-a_1)(x-a_2)\cdots(x-a_k) + 1</math>, který je zřejmě stupně alespoň 1 a přitom žádný z <big>\(a_1,a_2,\dots,a_k</math> není jeho kořenem.
+* Žádné konečné těleso není [[algebraicky uzavřené těleso|algebraicky uzavřené]] neboť označíme-li prvky konečného tělesa po řadě <big>\(a_1,a_2,\dots,a_k\)</big>, můžeme zkonstruovat mnohočlen<big>\((x-a_1)(x-a_2)\cdots(x-a_k) + 1\)</big>, který je zřejmě stupně alespoň 1 a přitom žádný z <big>\(a_1,a_2,\dots,a_k\)</big> není jeho kořenem.
 == Reprezentace ==
-<big>\(GF(p)</math> jsou celá čísla modulo dané prvočíslo <big>\(p</math> neboli <big>\(Z_p</math>. Typická reprezentace Galoisova tělesa <big>\(GF(p^k)</math> jsou [[polynom]]y nad <big>\(Z_p</math> modulo definiční polynom stupně <big>\(k</math>. Těleso tímto způsobem dostaneme právě když je definiční polynom [[ireducibilní polynom|ireducibilní]].
+<big>\(GF(p)\)</big> jsou celá čísla modulo dané prvočíslo <big>\(p\)</big> neboli <big>\(Z_p\)</big>. Typická reprezentace Galoisova tělesa <big>\(GF(p^k)\)</big> jsou [[polynom]]y nad <big>\(Z_p\)</big> modulo definiční polynom stupně <big>\(k\)</big>. Těleso tímto způsobem dostaneme právě když je definiční polynom [[ireducibilní polynom|ireducibilní]].
 Ne vždy je ''x'' primitivním prvkem tělesa (generátorem multiplikativní [[grupa|grupy]]). Například pro GF(3<sup>2</sup>) při definičním polynomu ''x''<sup>2</sup>+1 generuje pouze polovinu prvků a jako generátor je potřeba vzít ''x''+1. Při definičním polynomu ''x''<sup>2</sup>+''x''-1 ale ''x'' stačí.
@@ Řádka 17: / Řádka 17: @@
 === Využití v kódování ===
-V kódování jsou nejčastěji používána <big>\(GF(2^{2^k})</math>. V takovém případě je používán izomorfismus mezi číslem dle jeho <big>\(2^k</math> bitového zápisu na polynomy nad bity tak, že bit řádu <big>\(\ell</math> určuje koeficient u <big>\(x^\ell</math>.
+V kódování jsou nejčastěji používána <big>\(GF(2^{2^k})\)</big>. V takovém případě je používán izomorfismus mezi číslem dle jeho <big>\(2^k\)</big> bitového zápisu na polynomy nad bity tak, že bit řádu <big>\(\ell\)</big> určuje koeficient u <big>\(x^\ell\)</big>.
 Pozor, ač jsou při různé volbě definičního polynomu odpovídající tělesa [[isomorfismus|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 <big>\(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 <big>\(\alpha=x</math> resp. v číselném pohledu <big>\(\alpha=2</math>.
+Při výpočtech nad <big>\(GF(2^{2^k})\)</big> sčítání odpovídá bitový xor. Pro násobení je nejjednodušší vytvořit si tabulky logaritmů a exponentů primitivního prvku tělesa <big>\(\alpha=x\)</big> resp. v číselném pohledu <big>\(\alpha=2\)</big>.
-Tabulky logaritmů vytváříme na základě tabulky exponentů. Tabulku exponentů vyplňujeme postupně. Je-li <big>\(y</math> reprezentace <big>\(\alpha^\ell</math>, pak reprezentaci <big>\(\alpha^{\ell+1}</math> dostaneme buď jako <big>\(2y</math>, pokud je <big>\(2y<2^{2^k}</math> nebo pomocí xor s číslem odpovídajícím definičnímu polynomu (pokud <big>\(2y\ge2^{2^k}</math>).
+Tabulky logaritmů vytváříme na základě tabulky exponentů. Tabulku exponentů vyplňujeme postupně. Je-li <big>\(y\)</big> reprezentace <big>\(\alpha^\ell\)</big>, pak reprezentaci <big>\(\alpha^{\ell+1}\)</big> dostaneme buď jako <big>\(2y\)</big>, pokud je <big>\(2y<2^{2^k}\)</big> nebo pomocí xor s číslem odpovídajícím definičnímu polynomu (pokud <big>\(2y\ge2^{2^k}\)</big>).
-Máme-li jak tabulky logaritmů, tak tabulky mocnin primitivního prvku, můžeme násobení počítat (pro nenulové činitele <big>\(a,b</math>) pomocí <big>\(\alpha^{\log a+\log b}</math>. Je-li jakýkoli činitel nulový, je samozřejmě i součin nulový.
+Máme-li jak tabulky logaritmů, tak tabulky mocnin primitivního prvku, můžeme násobení počítat (pro nenulové činitele <big>\(a,b\)</big>) pomocí <big>\(\alpha^{\log a+\log b}\)</big>. Je-li jakýkoli činitel nulový, je samozřejmě i součin nulový.
 == Externí odkazy ==