Galoislichaam GF(16)

Het galoislichaam (Nederlands) / galoisveld (Belgisch) $\mathrm {GF} (16)$, ook genoteerd als $\mathbb {F} _{16}$, is het eindige lichaam/veld van orde 16, dus met 16 elementen. Het is een uitbreiding van graad vier van het lichaam/veld $\mathrm {GF} (2)$ met alleen de elementen 0 en 1, en de optelling modulo 2. De karakteristiek van $\mathrm {GF} (16)$ is daarmee ook 2. De uitbreiding $\mathrm {GF} (16)$ kan op verschillende manieren worden geconstrueerd. Dat kan onder meer op de manier waarop de complexe getallen als uitbreiding van de reële getallen worden geconstrueerd door toevoeging van een nieuw element $i$ dat voldoet aan $i^{2}+1=0$ of door de voorstelling als een lineaire ruimte met vermenigvuldiging, waarbij een algebra wordt ingevoerd.

Gelijkstellen

Voeg aan $\mathrm {GF} (2)$ een nieuw element $\alpha$ toe dat $\mathrm {GF} (16)$ voortbrengt. Daarmee zijn alle machten van $\alpha$ elementen van $\mathrm {GF} (16)$ bepaald en moeten de eerste 14 machten verschillend zijn aan 1. Dan kan het niet anders dat $\alpha ^{15}=1$.

$\mathrm {GF} (16)=\{0,\ 1,\ \alpha ,\ \alpha ^{2},\ \alpha ^{3},\ \ldots ,\ \alpha ^{14}\ \}$

Het nieuwe element $\alpha$ is dus een eenheidswortel. Omdat $\alpha$ voortbrenger is, kunnen de elementen $\alpha ^{2}$ en $\alpha ^{3}$ niet als lineaire combinatie van lagere machten worden uitgedrukt. $\mathrm {GF} (16)$ bestaat uit de lineaire combinaties van $1,\ \alpha ,\ \alpha ^{2}$ en $\alpha ^{3}$. Een element $m\in \mathrm {GF} (16)$ is dus van de vorm:

$m=m_{3}\alpha ^{3}+m_{2}\alpha ^{2}+m_{1}\alpha +m_{0}$

met $m_{i}\in \mathrm {GF} (2)$, dus 0 of 1.

Merk op dat de vier coëfficiënten als een vector kunnen worden opgevat.

Het element $\alpha ^{4}$ en ook alle hogere machten moeten in de lagere machten van $\alpha$ kunnen worden uitgedrukt

$\alpha ^{4}=k_{3}\alpha ^{3}+k_{2}\alpha ^{2}+k_{1}\alpha +k_{0}$

Dat betekent dat $\alpha$ een wortel is van een irreducibel polynoom

$x^{4}+k_{3}x^{3}+k_{2}x^{2}+k_{1}x+k_{0}$

In $\mathrm {GF} (2)[x]$ zijn drie van de 16 vierdegraadspolynomen irreducibel, namelijk

$f_{1}(x)=x^{4}+x+1$

$f_{2}(x)=x^{4}+x^{3}+1$

$f_{3}(x)=x^{4}+x^{3}+x^{2}+x+1$

want het zijn geen kwadraten en er is geen nulpunt.

Als reducerende vergelijking komen dus in aanmerking:

$\alpha ^{4}=\alpha +1$

$\alpha ^{4}=\alpha ^{3}+1$

$\alpha ^{4}=\alpha ^{3}+\alpha ^{2}+\alpha +1$

Met $f_{1}$

Noem de voortbrenger $\alpha$. De reducerende vergelijking is

$\alpha ^{4}=\alpha +1$

In berekeningen wordt $\alpha ^{4}$ steeds gelijkgesteld aan $\alpha +1$. Zo is bijvoorbeeld:

$\alpha ^{10}=(\alpha ^{4})^{2}\alpha ^{2}=(\alpha +1)^{2}\alpha ^{2}=(\alpha ^{2}+1)\ \alpha ^{2}=\alpha ^{4}+\alpha ^{2}=\alpha ^{2}+\alpha +1$

De $\alpha ^{k}$ met $\ k=1,\ 2,\ 4,\ 7,\ 8,\ 11,\ 13,\ 14\$ zijn ook voortbrengers.

Verder

$(x+\alpha )(x+\alpha ^{2})(x+\alpha ^{4})(x+\alpha ^{8})=x^{4}+x+1$

de wortels zijn voortbrengers.

De andere voortbrengers zijn wortels van

$(x+\alpha ^{7})(x+\alpha ^{14})(x+\alpha ^{13})(x+\alpha ^{11})=x^{4}+x^{3}+1$

Machten 

$0010\sim \alpha$

$0100\sim \alpha ^{2}$

$1000\sim \alpha ^{3}$

$0011\sim \alpha ^{4}=\alpha +1$

$0110\sim \alpha ^{5}=\alpha ^{2}+\alpha$

$1100\sim \alpha ^{6}=\alpha ^{3}+\alpha ^{2}$

$1011\sim \alpha ^{7}=\alpha ^{3}+\alpha +1$

$0101\sim \alpha ^{8}=\alpha ^{2}+1$

$1010\sim \alpha ^{9}=\alpha ^{3}+\alpha$

$0111\sim \alpha ^{10}=\alpha ^{2}+\alpha +1$

$1110\sim \alpha ^{11}=\alpha ^{3}+\alpha ^{2}+\alpha$

$1111\sim \alpha ^{12}=\alpha ^{3}+\alpha ^{2}+\alpha +1$

$1101\sim \alpha ^{13}=\alpha ^{3}+\alpha ^{2}+1$

$1001\sim \alpha ^{14}=\alpha ^{3}+1$

$0001\sim \alpha ^{15}=1$

Als voorbeeld nog de berekening

$(\alpha ^{3}+\alpha +1)(\alpha ^{2}+\alpha +1)=\alpha ^{5}+\alpha ^{4}+\alpha ^{3}+\alpha ^{3}+\alpha ^{2}+\alpha +\alpha ^{2}+\alpha +1=$

$=\alpha \ \alpha ^{4}+\alpha ^{4}+1=(\alpha +1)^{2}+1=\alpha ^{2}$

Met $f_{2}$

Noem de voortbrenger $\beta$. De reducerende vergelijking is

$\beta ^{4}=\beta ^{3}+1$

Verder

$(x+\beta )(x+\beta ^{2})(x+\beta ^{4})(x+\beta ^{8})=x^{4}+x^{3}+1$

de wortels zijn voortbrengers.

Omdat in de voorstelling met $f_{1}$:

$(x+\alpha ^{7})(x+\alpha ^{14})(x+\alpha ^{13})(x+\alpha ^{11})=x^{4}+x^{3}+1$

volgt dat:

$\beta =\alpha ^{7},\ \alpha ^{14},\ \alpha ^{13}{\text{ of }}\alpha ^{11}$

Machten 

$\beta$

$\beta ^{2}$

$\beta ^{3}$

$\beta ^{4}=\beta ^{3}+1$

$\beta ^{5}=\beta ^{3}+\beta +1$

$\beta ^{6}=\beta ^{3}+\beta ^{2}+\beta +1=(\beta +1)^{3}$

$\beta ^{7}=\beta ^{2}+\beta +1$

$\beta ^{8}=\beta ^{3}+\beta ^{2}+\beta$

$\beta ^{9}=\beta ^{2}+1$

$\beta ^{10}=\beta ^{3}+\beta$

$\beta ^{11}=\beta ^{3}+\beta ^{2}+1$

$\beta ^{12}=\beta +1$

$\beta ^{13}=\beta ^{2}+\beta$

$\beta ^{14}=\beta ^{3}+\beta ^{2}$

$\beta ^{15}=1$

Met $f_{3}$

$\mathrm {GF} (2)[x]/(x^{4}+x^{3}+x^{2}+x+1)$ is ook een lichaam.

De reducerende vergelijking is

$\gamma ^{4}=\gamma ^{3}+\gamma ^{2}+\gamma +1$

Er geldt

$\gamma ^{5}=\gamma ^{4}+\gamma ^{3}+\gamma ^{2}+\gamma =1$

Het element $\gamma$ is geen voortbrenger, maar $\gamma +1$ wel.

$\gamma ^{4}=\gamma ^{3}+\gamma ^{2}+\gamma +1=(\gamma +1)^{3}$

dus

$(\gamma +1)^{4}=(\gamma +1)^{3}+1$

Toevoegen van $\gamma +1$, dus van $\gamma$, is hetzelfde als toevoegen van $\beta$.

$\gamma =\beta +1$

Verder

$(x+\gamma )(x+\gamma ^{2})(x+\gamma ^{4})(x+\gamma ^{8})=x^{4}+x^{3}+x^{2}+x+1$

Machten 

$\gamma +1$

$(\gamma +1)^{2}=\gamma ^{2}+1$

$(\gamma +1)^{3}=\gamma ^{3}+\gamma ^{2}+\gamma +1=\gamma ^{4}$

$(\gamma +1)^{4}=\gamma ^{4}+1=\gamma ^{3}+\gamma ^{2}+\gamma$

$(\gamma +1)^{5}=\gamma ^{4}+\gamma =\gamma ^{3}+\gamma ^{2}+1$

$(\gamma +1)^{6}=\gamma ^{8}=\gamma ^{3}$

$(\gamma +1)^{7}=\gamma ^{4}+\gamma ^{3}=\gamma ^{2}+\gamma +1$

$(\gamma +1)^{8}=\gamma ^{8}+1=\gamma ^{3}+1=$

$(\gamma +1)^{9}=\gamma ^{4}+\gamma +\gamma ^{3}+1=\gamma ^{2}$

$(\gamma +1)^{10}=\gamma ^{3}+\gamma ^{2}$

$(\gamma +1)^{11}=\gamma ^{4}+\gamma ^{2}=\gamma ^{3}+\gamma +1$

$(\gamma +1)^{12}=\gamma$

$(\gamma +1)^{13}=\gamma ^{2}+\gamma$

$(\gamma +1)^{14}=\gamma ^{3}+\gamma$

$(\gamma +1)^{15}=1$

Verder geldt:

$\gamma =\beta +1=\alpha ^{14}+1=\alpha ^{3}$

Als algebra

$\mathrm {GF} (16)$ kan ook worden voorgesteld als een vierdimensionale lineaire ruimte met een vermenigvuldiging over $\mathrm {GF} (2)$ en met de optelling modulo 2 en de vermenigvuldiging bepaald door:

$(k_{3},k_{2},k_{1},k_{0})\cdot (0,0,0,1)=(k_{3},k_{2},k_{1},k_{0})$

$(0,k_{2},k_{1},k_{0})\cdot (0,0,1,0)=(k_{2},k_{1},k_{0},0)$

$(1,0,0,0)\cdot (0,0,1,0)=(0,0,1,1)$

Dan is

$(0,0,0,0)=0$

$(0,0,0,1)=1$

Noemt men

$(0,0,1,0)=\alpha$

dan komt de laatste regel voor de vermenigvuldiging op de reductie neer:

$\alpha ^{4}=\alpha ^{3}\cdot \alpha =\alpha +1$

en is ieder element $\mathrm {GF} (16)$ weer een lineaire combinatie van de vorm

$k=k_{3}\alpha ^{3}+k_{2}\alpha ^{2}+k_{1}\alpha +k_{0}$

De voorbeeldberekening gaat op dezelfde manier als de berekening in de binaire representatie.

Binair

De vectoren in de tweede representatie kunnen ook als nibbles worden gezien met als optelling de operatie exclusieve disjunctie XOR en 0001 = 1. De vermenigvuldiging met 0010 is een linksverschuiving. Overflow resulteert in bijtellen van 0011.

De voorbeeldberekening verloopt als volgt:

$(1000+0010+0001)(0100+0010+0010)=$

$=\ (1000+0010+0001)\cdot 0100\ +$

$\ +(1000+0010+0001)\cdot 0010\ +$

$\ +(1000+0010+0001)\cdot 0001\ \ =$

$=\ 0110+1000+0100\ +$

$\ +0011+0100+0010\ +$

$\ +1000+0010+0001\ \ =$

$=\ 1010+0101+1011=0100$

Met veeltermen

Een vierde mogelijke representatie van $\mathrm {GF} (16)$ is met polynomen over $\mathrm {GF} (2)$ als elementen. Een element $k\in \mathrm {GF} (16)$ heeft dan de vorm:

$k(x)=k_{3}x^{3}+k_{2}x^{2}+k_{1}x+k_{0}$

met $k_{i}\in \mathrm {GF} (2)$, dus 0 of 1. Optellen modulo 2 en vermenigvuldigen gaan op de gebruikelijke manier. Het identieke polynoom $x$ is dan een voortbrenger. Het is ook nu weer de vraag hoe $x^{4}$ moet worden gereduceerd. $x^{4}=x+1$ is ook hier een van de mogelijkheden, wat betekent dat modulo $x^{4}+x+1$ wordt gerekend. Het identieke polynoom $f(x)=x$ komt overeen met het nieuwe element $\alpha$ in de eerste representatie.

Deze voorstelling is in wezen gelijk aan de constructie van de factorring $\mathbb {GF} (2)[x]/(x^{4}+x+1)$.

De voorbeeldberekening vertoont veel overeenkomsten met het eerste geval:

$(x^{3}+x+1)(x^{2}+x+1)=x^{5}+x^{4}+x^{3}+x^{3}+x^{2}+x+x^{2}+x+1=$

$=x^{4}(x+1)+1=(x+1)^{2}+1=x^{2}$

GF(8)

Volgens een stelling is het lichaam/veld $\mathrm {GF} (p^{n})$ alleen dan een deellichaam $\mathrm {GF} (p^{m})$ als $m$ door $n$ kan worden gedeeld.

Dus is $\mathrm {GF} (8)=\mathrm {GF} (2)[x]/(x^{3}+x+1)$ geen deellichaam van $\mathrm {GF} (16)$.

De multiplicatieve groep is cyclisch. Noem een voortbrenger $b$

De reducerende vergelijking is:

$b^{3}=b+1$

$\mathrm {GF} (8)=\{0,\ 1,\ b,\ b^{2},\ b^{3},\ b^{4},\ b^{5},\ b^{6}\}$

met

$b^{3}=b+1$

$b^{4}=b^{2}+b$

$b^{5}=b^{3}+b^{2}=b^{2}+b+1$

$b^{6}=(b^{3})^{2}=b^{2}+1$

$b^{7}=b^{3}+b=1$

GF(4)

Het lichaam/veld $\mathrm {GF} (4)$ is wel een deellichaam van $\mathrm {GF} (16)$

$\mathrm {GF} (4)=\{0,1,p,q\}$

met

$p+q=1;\ p^{2}=q;\ p^{3}=pq=1;\ q^{2}=p$

$p^{2}+p+1=0$

verband met

$\mathrm {GF} (16):\ p=\alpha ^{k}$

$\alpha ^{2k}+\alpha ^{k}+1=0$

$k=5,\ k=10$

Twee voortbrengers van $\mathrm {GF} (4)$

$\alpha ^{5},\ \alpha ^{10}$

$\mathrm {GF} (4)$ is een deellichaam van $\mathrm {GF} (16)$, maar niet van $\mathrm {GF} (8)$.

Literatuur

• JH van Lint en J Seidel. Discrete wiskunde, 1973. voor de Technische Universiteit Eindhoven