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.
