Generování konečných těles
Definice tělesa:
Tělesem nazýváme nějakou množinu (její prvky nazýváme skaláry) spolu se dvěma binárními operacemi (sčítání a násobení), které splňují následujících deset podmínek (axiomů):
(A1) Sčítání v tělese je komutativní: a + b = b + a
(A2) Sčítání v tělese je asociativní: ( a + b ) + c = a + ( b + c )
(A3) Existuje skalár 0 takový, že: a + 0 = 0 + a = a pro každý skalár a.
(A4) Ke každému skaláru a existuje skalár -a takový, že: a + (-a) = 0
(B1) Násobení v tělese je komutativní: a * b = b * a
(B2) Násobení v tělese je asociativní: ( a * b ) * c = a * ( b * c )
(B3) Existuje skalár 1 takový, že: a * 1 = 1 * a = a
(B4) Ke každému skaláru a kromě 0 existuje skalár a-1 takový, že: a * a-1 = 1
(C) Násobení je distributivní vzhledem ke sčítání: a * ( b + c ) = ( a * b ) + ( a * c )
(D) Skalár 0 se nerovná skaláru 1
Tělesa racionálních, reálných či komplexních čísel jsou všem dobře známa. Množina celých ani přirozených čísel netvoří těleso (nesplňují například B4). Zajímavá je ale možnost vytvoření tělesa nad konečnou množinou. K tomu je třeba vhodným způsobem nadefinovat sčítání a násobení. Tím se zabývá tento článek. Uváděná tvrzení přijměte prosím jako fakt, neboť není cílem tohoto textu je dokazovat. Některé z těch důkazů najdete ve skriptech doktora Jiřího Tůmy nebo jiných. Pro zápis operací v tělese obvykle nepoužíváme definitorické rovnice pro sčítání a násobení, ale dvě tabulky. Například pro těleso nad množinou {0,1,2} píšeme:
| + |
0 |
1 |
2 |
|
|
|
|
* |
0 |
1 |
2 |
| 0 |
0 |
1 |
2 |
|
|
|
|
0 |
0 |
0 |
0 |
| 1 |
1 |
2 |
0 |
|
|
|
|
1 |
0 |
1 |
2 |
| 2 |
2 |
0 |
1 |
|
|
|
|
2 |
0 |
2 |
1 |
Máme-li n-prvkovou množinu, pak těleso nad ní existuje, právě když n = pm, kde p je nějaké prvočíslo a m libovolné přirozené číslo (ne 0, neplatil by axiom D). Všechna n-prvková tělesa jsou izomorfní. Jinými slovy: pro daný počet prvků existuje jediný způsob jak definovat sčítání a násobení. Je-li m = 1 (máme prvočíselný počet skalárů), pak sčítání i násobení je definováno jednoduše jako tzv. zbytkové třídy modulo p. Pokud se ale m nerovná 1, je způsob konstrukce aditivní a multiplikativní tabulky poněkud složitější. Například čtyřprvkové těleso vypadá takhle:
| + |
0 |
1 |
2 |
3 |
|
|
|
|
* |
0 |
1 |
2 |
3 |
| 0 |
0 |
1 |
2 |
3 |
|
|
|
|
0 |
0 |
0 |
0 |
0 |
| 1 |
1 |
0 |
3 |
2 |
|
|
|
|
1 |
0 |
1 |
2 |
3 |
| 2 |
2 |
3 |
0 |
1 |
|
|
|
|
2 |
0 |
2 |
3 |
1 |
| 3 |
3 |
2 |
1 |
0 |
|
|
|
|
3 |
0 |
3 |
1 |
2 |
Budeme konstruovat n-prvkové těleso ( n = pm, kde p je prvočíslo). Mějme množinu M všech polynomů jedné proměnné stupně menšího než m, jejichž koeficienty jsou z množiny N = { 0, 1, ... , p-1 }. Taková množina má přesně n-prvků. Tyto polynomy vezmeme jako skaláry a budeme na nich definovat operace sčítání a násobení tak, aby výsledný polynom byl opět z množiny M.
Aditivní tabulku (sčítání) lze generovat velmi jednoduše. Stačí totiž sčítat příslušné koeficienty polynomů modulo p. Tabulku pro násobení vytvoříme podobně. Vynásobíme polynomy tak, jak je běžné, a koeficienty převedeme do množiny N operací modulo p. Jenže výsledný polynom (označme ho X) může být stupně vyššího než m. K odstranění tohoto nedostatku našeho výsledku budeme potřebovat nějaký ireducibilní polynom stupně m, to jest takový, který nelze rozložit na součin jednodušších. Máme-li takový polynom, vydělíme jím polynom X. Takové dělení dává nějaký polynom jako podíl a nějaký jiný jako zbytek. Vezmeme tento zbytek a převedeme jeho koeficienty do N operací modulo p. A máme výsledek. ;-)
Trochu nesrozumitelné, že? Následuje názorná ukázka. Budu generovat těleso o 27 prvcích. Tedy n = 27, p = 3, m = 3. Jako skaláry použiju polynomy stupně maximálně m-1 = 2, jejichž koeficienty budou 0,1,2 (0 až p-1). A teď mám-li například sečíst polynom x2 + x + 1 a polynom 2x2 + x, budu sčítat koeficienty u stejných mocnin, a pokud dostanu číslo větší než 2, odečtu trojku. Výsledek je tedy 2x + 1. S násobením je to o něco složitější. Budu násobit řekněme x2 + 2x + 1 a 2x2 + x. Nejprve vynásobím klasicky a dostávám 2x4 + 5x3 + 4x2 + x. Teď přepočítám koeficienty modulo p = 3 a dostanu 2x4 + 2x3 + x2 + x. To je ale pořád polynom stupně 4. Pro korekci budu potřebovat polynom stupně 3, který je ireducibilní. Například x3 + x2 + x + 2. Teď standardním postupem vydělím, dostanu 2x a zbytek -x2 - 3x. Vezmu zbytek a přepočítám koeficienty modulo 3. Dostanu 2x2. To je výsledek.
Nezáleží na tom, jaký zvolíme polynom pro korekci, jediný požadavek je, aby byl ireducibilní. Při jiné volbě polynomu dostaneme izomorfní tělesa. To znamená, že lze skaláry přejmenovat tak, že se multiplikativní tabulky převedou jedna na druhou. A pokud se vám nelíbí, že skaláry vašeho tělesa jsou polynomy a ne čísla, zkuste je označit pořadím v lexikografickém uspořádání podle koeficientů. Zjistíte, že nula se opravdu chová jako prvek neutrální vzhledem ke sčítání a jednička jako neutrální vzhledem k násobení. Přesně podle definice. Správnost popsaného algoritmu se dá poměrně snadno dokázat, ale to není cílem tohoto textu.
Dal bych sem svůj zdroják ke stažení, ale má to ještě jednu chybu. Nemám algoritmicky vyřešené hledání ireducibilního polynomu daného stupně. Pokud byste měli návrh na efektivní řešení, budu vděčný, když mi napíšete.
Konečná tělesa mají v matematice mnoho uplatnění. Pokud se ale přesto ptáte, k čemu je to vůbec dobré, mohu posloužit příkladem (viz osmou kapitolu skript docenta Tůmy). Přenos digitálních dat nejrůznějšími komunikačními kanály má vždy určitou chybovost. Tu lze výrazně snížit (o několik řádů) použitím tzv. samoopravných kódů. Je to způsob kódování přenášených dat, který umožňuje rekonstruovat informaci poškozenou šumem. Takový kód lze matematicky popsat jako vektorový prostor nad vhodným konečným tělesem. Například NASA používá pro přenos dat z kosmických sond kód, jehož základem je těleso o 256 prvcích. Myslím, že je to velmi zajímavá praktická motivace. Další oblastí, která se dnes bez konečných těles neobejde je šifrování. V současnosti nejpoužívanější systém pro šifrování a elektronické podpisy je PGP.
Odkazy:
Jak pracuje PGP
O principu šifry RSA
Special thanx goes to Luboš Motl. Připomínky posílejte mailem na adresu egg@matfyz.cz.
Můžete se vrátit zpět na homepage anebo tam, odkud jste přišli.
