Konečná tělesa a jejich rozšíření
Tomáš Kalvoda & Štěpán Starosta, KAM FIT ČVUT, 2014-2017
V tomto worksheetu shrneme různé užitečné nástroje pro práci s konečnými tělesy v SageMath.
Příkazy pro konstrukci konečného tělesa
V SageMath máme k dispozici příkaz GF
(alias pro FiniteField
). Chceme-li například pracovat v konečném tělese s prvočíselným počtem prvků, můžeme toto těleso ihned vytvořit následujícím příkazem.
V se sčítá a násobí modulo . Počítání v tomto konečném tělese funguje jak by člověk očekával.
Dále nám SageMath umožňuje konstruovat konečná tělesa s řádem, který je neprvočíselný, tedy mocninou nějakého prvočísla . Již víme jak tato tělesa konstruovat pomocí faktorizace. Nyní si ukážeme možnosti funkce GF
. Zkonstruujme těleso řádu , kde jsme si zvolili dříve a .
Pozor! Přikonstrukci tělesa neprvočíselného řádu je nutné SageMath říct, jak budeme označovat proměnnou příslušných polynomů. (Tomuto prvku se v SageMath také říká generátor, není to ovšem (obecně) generátor multiplikativní grupy!) Pokud Vám syntax v předchozí buňce přijde podivná, lze použít alternativní zápis:
Pokud SageMath neřekneme, v jakém modulu chceme pracovat, sám zvolí ireducibilní (nad ) polynom požadovaného řádu . Jsme-li zvědaví, můžeme si tento polynom snadno zjistit.
Podobně jako v předchozím příkladě (těleso prvočíselného řádu) se podívejme jak lze provádět algebraické operace v tomto konečném tělese. Nejprve zkonstuujme dva prvky tělesa .
Poznamenejme, že v prvním případě SageMath pozná, že mluvíme o prvku , protože jsme použili 'x' k označení formální proměnné polynomů. Například následující pokusy zřejmě nefungují.
Několik pokusných algebraických operací.
Na algebraických operacích není tedy nic překvapivého. SageMath nám ale umožňuje zjistit zajímavé informace o tělese samotném. Už jsme si ukázali, jak zjistit modul, vůči kterému počítáme. Dále máme k dispozici následující vlastnosti tělesa . Začněme několika základními.
Na každé těleso se můžeme dívat jako na rozšíření jeho prvotělesa.
O multiplikativní grupě tělesa , víme, že je cyklická. Sage nám umožňuje hledat její generátory (tzv. primitivní prvky).
Ověřme, že je skutečně generátorem. Stačí (a v našem případě to stále ještě lze) ověřit, že negeneruje netriviální podgrupu. (Ověření provedeme poměrně brutální metodou...)
Vidíme, že výsledek dostáváme pouze pro poslední prvek seznamu (což je řád multiplikativní grupy). Pro netriviální dělitele nezískáváme a proto negeneruje grupu menšího řádu.
Hledání primitivního prvku je zajímavější úloha. Podívejme se, jak ji SageMath vykonává.
Metoda gen
nevrací generátor ve smyslu generátoru cyklické grupy, ale generátor ve smyslu matematického objektu SageMath. V našem případě jsem výše tento prvek označili symbolem xx
. V této konstrukci jde obecně přímo o formální proměnnou polynomů, se kterými pracujeme.
Z posledních několika řádků metody multiplicative_generator
je vidět, že hledání primitivního prvku v SageMath není nijak sofistikované, naopak... Tedy je prostor pro zlepšení.
Druhou variantou je použít konstruktor konečného tělesa takto GF(5^40, modulus="primitive")
. Bude nám vybrán polynom, jehož kořen bude primitivním prvkem a nebude co počítat.
Na závěr znovu poznamenejme, jak lze vytvořit konečné těleso řádu , s vlastním ireducibilním polynomem. Existují dvě možnosti. První možností je přímo použít faktorizační proceduru:
Druhou možností je opět použití příkazu GF
.
Rozšíření těles
Konstrukce rozšíření
Z přednášky víme, že každé těleso lze chápat jako vektorový prostor nad libovolným jeho podtělesem . Těleso pak také nazýváme rozšířením tělesa . V této sekci si ukážeme některé pojmy z přednášky na konkrétním příkladě .
Sage automaticky chápe jako jednoduché rozšíření jeho prvotělesa .
Z přednášky víme, že je podtělesem , právě když je dělitel čísla 8. má proto pouze podtělesa pro následující (zahrnujeme i triviální podtělesa).
Uvažme jakožto rozšíření .
Buď okruh polynomů v proměnné nad .
Zvolme ireducibilní polynom z .
Hledané rozšíření tělesa pak získáme faktorizací okruhu vůči hlavnímu ideálu generovanému .
Polynomiální a normální báze
V této části si ukážeme, jak lze na využít struktury vektorového prostoru v tělesech. Nejprve se budeme věnovat polynomiálním a poté normálním bázím.
Polynomiální báze
Jako jednoduchý příklad uvažme těleso chápané jako vektorový prostor nad .
Sestrojení báze
Příslušný vektorový prostor označme symbolem . je tedy vektorový prostor nad .
Báze tvořená prvky se v tomto případě nazývá polynomiální bází.
Uvažme dva testovací prvky našeho tělesa .
Jejich souřadnice vzhledem k polynomiální bázi lze snadno získat pomocí příkazu _vector_.
Sčítání
Operace sčítání vektorů po složkách (v každé složce modulo 2) odpovídá sčítání v . Přesvědčíme se o tom například v následujícím pokusu.
Násobení
Násobení je komplikovanější. V obecném vektorovém prostoru neexistuje kanonický způsob násobení dvou vektorů s vektorovým výstupem (známý vektorový součin funguje pouze v ).
Náš vektorový prostor je ale zároveň tělesem. Pro fixní lze zobrazení chápat jako lineární zobrazení! Sestrojme jeho matici v naší polynomiální bázi. SageMath má pro tento účel dokonce rovnou zabudovanou funkci. Pro další referenci si tuto matici označme .
Součinu v pak odpovídá vektor , kde pod máme na mysli vektorovou reprezentaci .
Připomeňme, jak lze matici lineárního zobrazení sestrojit (bez odvolání se na příkaz _matrix_
). Sloupce matice představují součiny a vektorů polynomiální báze v polynomiální bázi. Přesněji:
Alternativní metodou je vyjádřit násobení jako bilineární zobrazení . Je-li standardní báze, pak pro součin dvou vektorů a platí kde a jsou souřadnice a vzhledem k a tečka označuje násobení v .
Násobení pak provedeme “obložením” takto jednou napočtené matice a souřadnicemi příslušných vektorů. Protože jsme v matici nechali rovnou výrazy z , dostaneme rovnou polynomiální výsledek.
Normální báze
Ve vektorovém prostoru máme nepřeberné množství různých bází. Pro různé operace může být výhodnější používat vhodně zvolenou bázi. V normálních bázích se například snadno mocní. Opět budeme pracovat v chápaném jako vektorový prosto nad .
Zvolme nyní následující prvek tělesa .
Normální báze je báze tvaru . Je nutné ověřit, že tento soubor je lineárně nezávislý a tvoří skutečně bázi! To není automaticky splněno (zvolte např. ).
Otestujme lineární nezávislost (případně máme i kritérium z přednášky).
Námi zvolený soubor proto skutečně tvoří bázi. Pro snadné počítání se souřadnicemi vzhledem k této bázi nám Sage poskytuje následující metody.
Z přednášky víme, že mocnění lze v normální bázi realizovat jako pouhé cyklické posunutí souřadnic. Ověřme si to na našem příkladě. Vypočtěme souřadnice mocnin .
Na závěr poznamenejme, že operace sčítání opět působí jednoduše po složkách. Operace obyčejného násobení v normální bázi nemá žádné zvláštní vlastnosti. Mocnění má výše pozorovnanou vlastnost pouze, pokud mocníme na řád příslušného podtělesa.
Ukázka práce nad větším podtělesem
Uvažme opět a chápejme ho jako rozšíření tělesa . Tento příklad jsme uvažovali již v předcházejícím textu, proto pouze rychle vytvoříme potřebné objekty.
Vektorový prostor nad dimenze , tj. stupně definujícího prvku .
Polynomiální báze.
Testovací element.
Nyní je potřeba dvou pomocných funkcí.
Podívejme se opět na operaci násobení v , pracujeme v polynomiální bázi.
Součin pomocí maticového násobení a ověření výpočtem v .