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 $GF(p)$ se sčítá a násobí modulo $p$. 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 $p$. Již víme jak tato tělesa konstruovat pomocí faktorizace. Nyní si ukážeme možnosti funkce GF. Zkonstruujme těleso řádu $p^n$, kde $p$ jsme si zvolili dříve a $n = 5$.

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 $GF(p)$) polynom požadovaného řádu $n$. 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 $T$.

Poznamenejme, že v prvním případě SageMath pozná, že mluvíme o prvku $T$, 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 $T$ 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 $T$. 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 $T$, $T^* = (T\smallsetminus\{0\},\cdot)$ víme, že je cyklická. Sage nám umožňuje hledat její generátory (tzv. primitivní prvky).

Ověřme, že $a = x$ 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 $1$ dostáváme pouze pro poslední prvek seznamu (což je řád multiplikativní grupy). Pro netriviální dělitele $1$ nezískáváme a $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á.

   File: /projects/sage/sage-7.5/src/sage/rings/finite_rings/finite_field_base.pyx
   Source:
       def multiplicative_generator(self):
        """
        Return a primitive element of this finite field, i.e. a generator
        of the multiplicative group.

        You can use :meth:`multiplicative_generator()` or
        :meth:`primitive_element()`, these mean the same thing.

        .. WARNING::

           This generator might change from one version of Sage to another.

        EXAMPLES::

            sage: k = GF(997)
            sage: k.multiplicative_generator()
            7
            sage: k.<a> = GF(11^3)
            sage: k.primitive_element()
            a
            sage: k.<b> = GF(19^32)
            sage: k.multiplicative_generator()
            b + 4

        TESTS:

        Check that large characteristics work (:trac:`11946`)::

            sage: p = 10^20 + 39
            sage: x = polygen(GF(p))
            sage: K.<a> = GF(p^2, modulus=x^2+1)
            sage: K.multiplicative_generator()
            a + 12
        """
        from sage.arith.all import primitive_root

        if self.__multiplicative_generator is not None:
            return self.__multiplicative_generator
        if self.degree() == 1:
            self.__multiplicative_generator = self(primitive_root(self.order()))
            return self.__multiplicative_generator
        n = self.order() - 1
        g = self.gen(0)
        # We check whether x+g is a multiplicative generator, where
        # x runs through the finite field.
        # This has the advantage that g is the first element we try,
        # so we always get g as generator if possible.  Second, the
        # PARI finite field iterator gives all the constant elements
        # first, so we try g+(constant) before anything else.
        for x in self:
            a = g+x
            if a != 0 and a.multiplicative_order() == n:
                self.__multiplicative_generator = a
                return a

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 $p^n$, 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 $T$ lze chápat jako vektorový prostor nad libovolným jeho podtělesem $K$. Těleso $K$ pak také nazýváme rozšířením tělesa $K$. V této sekci si ukážeme některé pojmy z přednášky na konkrétním příkladě $T = GF(2^8)$.

Sage automaticky chápe $GF(2^8)$ jako jednoduché rozšíření jeho prvotělesa $GF(2)$.

Z přednášky víme, že $GF(2^k)$ je podtělesem $GF(2^8)$, právě když $k$ je dělitel čísla 8. $GF(2^8)$ má proto pouze podtělesa $GF(2^k)$ pro následující $k$ (zahrnujeme i triviální podtělesa).

Uvažme $T$ jakožto rozšíření $K = GF(2^4)$.

Buď $R$ okruh polynomů v proměnné $z$ nad $K$.

Zvolme ireducibilní polynom z $R$.

Hledané rozšíření tělesa $K$ pak získáme faktorizací okruhu $R$ vůči hlavnímu ideálu generovanému $g$.

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 $T = GF(2^8)$ chápané jako vektorový prostor nad $GF(2)$.

Sestrojení báze

Příslušný vektorový prostor označme symbolem $V$. $V$ je tedy vektorový prostor $T$ nad $GF(2)$.

Báze tvořená prvky $(1,x,\ldots,x^7)$ se v tomto případě nazývá polynomiální bází.

Uvažme dva testovací prvky našeho tělesa $T$.

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 $T$. 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 $\mathbb{R}^3$).

Náš vektorový prostor je ale zároveň tělesem. Pro fixní $f$ lze zobrazení $g \mapsto f*g$ 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 $M_f$.

Součinu $f\cdot g$ v $T$ pak odpovídá vektor $M_f g$, kde pod $g$ máme na mysli vektorovou reprezentaci $g$.

Připomeňme, jak lze matici lineárního zobrazení sestrojit (bez odvolání se na příkaz _matrix_). Sloupce matice $M_f$ představují součiny $f$ 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í $V \times V \to V$. Je-li $\mathcal{B} = (b_0,b_1,\ldots,b_7)$ standardní báze, pak pro součin dvou vektorů $f$ a $g$ platí $$f \cdot g = \sum_{i=0}^7 \sum_{j=0}^7 f_i f_j (b_i \cdot b_j),$$ kde $(f_i)$ a $(f_j)$ jsou souřadnice $f$ a $g$ vzhledem k $B$ a tečka označuje násobení v $T$.

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 $T$, 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 $T = GF(2^8)$ chápaném jako vektorový prosto $V$ nad $GF(2)$.

Zvolme nyní následující prvek tělesa $T$.

Normální báze je báze tvaru $(a,a^{2},a^{2^2},\ldots,a^{2^7})$. 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ř. $a=1$).

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 $f^{2^i}$.

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 $T = GF(2^8)$ a chápejme ho jako rozšíření tělesa $GF(2^4)$. 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 $K$ dimenze $2$, tj. stupně definujícího prvku $g$.

Polynomiální báze.

Testovací element.

Nyní je potřeba dvou pomocných funkcí.

Podívejme se opět na operaci násobení v $T$, pracujeme v polynomiální bázi.

Součin pomocí maticového násobení a ověření výpočtem v $T$.