Costruzione di un campo di galois GF(4)

[raff5184]

Ciao, ho un esempio della costruzione di un campo di galois GF(4)

1) Scelgo un polinomio primitivo di grado 2
$g(X)= 1+X+X^2$ e 2) indico con $alpha$ una sua radice $g(alpha)=0$
Ora l'esempio mi dice che il campo che cerco è:

$GF(4) = {0, 1, alpha, (1+alpha)}$

Forse mi sfugge qualcosa nella costruzione del campo poiché non capisco perché sono riportati nel $GF(4)$ anche $alpha$ e $1+alpha$ (mi è noto che $g(alpha)=g(alpha+1)=0$)
La teoria che ho io mi dice che, fatti i passi 1 e 2 posso scrivere
$GF(2^m)={a_0+a_1alpha+a_2alpha^2+...+a_(m-1)alpha^(m-1): a_k in GF(2)}={(a_0, a_1, a_2,..., a_(m-1)), a_k in GF(2)}$

Per favore non usate un linguaggio troppo tecnico è appena la prima lezione sulle strutture algebriche

[j18eos]

Ma [tex]$g$[/tex] è un polinomio a coefficienti in che campo?

[raff5184]

"j18eos":Ma [tex]$g$[/tex] è un polinomio a coefficienti in che campo?

Galois binario GF(2)

[j18eos]

Mi sà che il libro costruisca [tex]$GF(4)=\mathbb{Z}_2(\alpha)$[/tex]!

[raff5184]

ho capito cosa fa. Prende tutti i polinomi di grado inferiore a quello dato. cioè tutte le possibili combinazioni di $a_0$ e $a_1$ (che possono essere 0 o 1) nel polinomio $a_0+a_1alpha$

[gugo82]

Cambierò un po' la notazione, giacché vogliamo lavorare in astratto e i simboli [tex]$0,\ 1$[/tex] fanno troppo pensare ai numeri; li rimpiazzerò con [tex]$o,\ i$[/tex] rispettivamente.
Tuttavia, questo rimpiazzamento non durerà a lungo.

Allora, innanzitutto [tex]$\mathbb{GF}(4)$[/tex] deve essere un campo, quindi deve contenere [tex]$o$[/tex] (neutro rispetto all'addizione) ed [tex]$i$[/tex] (neutro rispetto alla moltiplicazione) e tali elementi devono essere distinti.
Ovviamente, poi, il nostro campo dovrà contenere un'immagine di [tex]$\mathbb{Z}$[/tex], che si ottiene prendendo tutti i multipli di [tex]$i$[/tex] (ossia i numeri del tipo [tex]$n\cdot i =\underbrace{i+\ldots +i}_{\text{$n$ volte}}$[/tex], per [tex]$n$[/tex] positivo, e [tex]$n\cdot i=- (-n)\cdot i$[/tex], per [tex]$n$[/tex] negativo).
[N.B.: Quando parlo di addizione e moltiplicazione non ci sto dando ancora un senso preciso (tipo, l'addizione modulo [tex]$m$[/tex] o l'addizione in [tex]$\mathbb{Z}$[/tex]), giacché per forza di cose dobbiamo avere a che fare con simboli che non sono né numeri interi, né qualche altra cosa sensata (in generale).
Quando costruisci un campo (o qualunque altra struttura algebrica astratta) le operazioni vanno definite in maniera sensata ex post, ossia in modo da far tornare bene la costruzione.]

Poi sappiamo che vogliamo metterci dentro il simbolo [tex]$\alpha$[/tex]; per far tornare le cose, ci devo mettere dentro (per [tex]$n,m\in \mathbb{Z}$[/tex]) anche tutte le potenze di [tex]$\alpha$[/tex] (diciamole [tex]$\alpha^n$[/tex]), tutti i multipli di [tex]$\alpha$[/tex] (diciamoli [tex]$n\cdot \alpha$[/tex]), tutti i numeri del tipo [tex]$\alpha^n + m\cdot i$[/tex] o [tex]$n\cdot \alpha +m\cdot i$[/tex] e così via.

In particolare ci dobbiamo mettere dentro anche [tex]$\alpha +i$[/tex].

Quindi fin qui abbiamo visto perchè in [tex]$\mathbb{GF} (4)$[/tex] ci devono stare almeno i quattro elementi [tex]$o,i,\alpha ,\alpha +i$[/tex] più qualche altra zozzeria, come abbiamo detto sopra.

Ora, il problema è che noi vogliamo un campo d'ordine [tex]$4$[/tex], quindi quei quattro elementi devono bastarci a fare tutto qual che dobbiamo fare; in particolare, si tratta di scegliere le operazioni in modo che non ci siano in [tex]$\mathbb{GF} (4)$[/tex] più elementi di quelli che vogliamo (ossia [tex]$o,i,\alpha ,\alpha+i$[/tex]).

Cominciamo dalla moltiplicazione. Qui ci viene in aiuto il fatto che [tex]$g(\alpha )=0$[/tex] (almeno simbolicamente): infatti ciò significa che [tex]$\alpha^2 +\alpha +1=0$[/tex], ossia [tex]$\alpha^2 = -\alpha -1=\alpha +1$[/tex] (perchè i coefficienti del polinomio sono in [tex]$\mathbb{Z}_2$[/tex]), quindi sappiamo che è sensato porre [tex]$\alpha^2 =\alpha +1$[/tex]; ma [tex]$\alpha +1$[/tex] non sta in [tex]$\mathbb{GF} (4)$[/tex] come l'abbiamo costruito, quindi siamo forzati a fare l'identificazione [tex]$\alpha +1\cong \alpha +i$[/tex], ossia [tex]$i\cong 1$[/tex]; a questo punto, identifichiamo anche [tex]$o\cong 0$[/tex], per comodità.
Analogamente, da [tex]$g(\alpha +1)=0$[/tex] segue [tex]$(\alpha +1)^2=(\alpha +1) +1=\alpha$[/tex], e ciò ci dice che è sensato porre per definizione [tex]$(\alpha +1)^2=\alpha$[/tex].
L'ultimo nodo da sciogliere per costruire la tabella della moltiplicazione è stabilire quanto faccia [tex]$\alpha \cdot (\alpha +1)$[/tex]. Se notiamo che [tex]$g(X)=X (X+1)+1$[/tex] e ricordiamo che [tex]$g(\alpha)=0$[/tex], troviamo subito [tex]$\alpha (\alpha+1 )=-1=1$[/tex], che è quello che ci serviva.
In questo modo abbiamo la seguente tabella della moltiplicazione:

[tex]\begin{matrix} \cdot & 0 & 1 & \alpha & \alpha +1 \\
0 & 0 & 0 & 0 & 0 \\
1& 0 & 1 & \alpha & \alpha +1\\
\alpha & 0 & \alpha & \alpha +1 & 1 \\
\alpha +1 & 0 & \alpha +1 & 1 & \alpha \end{matrix}[/tex]

che, tra l'altro, mostra che la struttura [tex]$(\mathbb{GF}(4) ,\cdot)$[/tex] è un monoide commutativo con soli quattro elementi che ha invertibili [tex]$1,\alpha,\alpha +1$[/tex].
Inoltre, si vede che, essendo il monoide finito, gli elementi [tex]$\alpha$[/tex] ed [tex]$\alpha +1$[/tex] hanno ordine finito ed uguale a [tex]$3$[/tex]; per questo non c'è bisogno di aggiungere altre loro potenze nella costruzione di [tex]$\mathbb{GF} (4)$[/tex].

Poi c'è l'addizione.
Ora, sappiamo che [tex]$i\cong 1\in \mathbb{Z}_2$[/tex], quindi tanto vale porre [tex]$i+i\cong 1+1=0$[/tex]; in questo modo chi debba essere [tex]$(\alpha +1)+1$[/tex] lo si ricava subito: cioè [tex]$(\alpha +1)+1=\alpha +(1+1)=\alpha$[/tex]; analogamente converrà che [tex]$(\alpha +1)+(\alpha +1)=\alpha +\alpha +1+1=\alpha +\alpha$[/tex] e che [tex]$\alpha +(\alpha +1)=\alpha +\alpha +1$[/tex]; ora rimane da vedere cosa succede a [tex]$\alpha +\alpha$[/tex]: dalla moltiplicazione sappiamo che [tex]$\alpha (\alpha +1)=1$[/tex], ma anche che [tex]$\alpha^2 =\alpha +1$[/tex], quindi [tex]$1=\alpha^2+\alpha=(\alpha+1)+\alpha =\alpha +\alpha +1$[/tex] e perciò [tex]$\alpha +\alpha =0$[/tex].
Conseguentemente la seguente tabella dell'addizione:

[tex]\begin{matrix} + & 0 & 1 & \alpha & \alpha +1 \\
0 & 0 & 1 & \alpha & \alpha +1 \\
1& 1 & 0 & \alpha +1 & \alpha\\
\alpha & \alpha & \alpha +1 & 0 & 1 \\
\alpha +1 & \alpha +1 & \alpha & 1 & 0 \end{matrix}[/tex]

che mostra che [tex]$(\mathbb{GF} (4) ,+)$[/tex] è un gruppo commutativo con soli quattro elementi; inoltre tutti gli elementi hanno periodo [tex]$2$[/tex], quindi nella costruzione di [tex]$\mathbb{GF} (4)$[/tex] non c'è bisogno di aggiungere multipli di [tex]$1,\alpha,\alpha +1$[/tex].

Rimane da mostrare che [tex]$(\mathbb{GF} (4) ,+\cdot)$[/tex] è un anello, ossia che [tex]$\cdot$[/tex] è distributiva rispetto a [tex]$+$[/tex], ma questo si può fare a occhio.

Quindi [tex]$(\mathbb{GF} (4) ,+\cdot)$[/tex] è un campo che ha tutte le caratteristiche richieste.

Ovviamente, non essendo un esperto, potrebbero esserci scritte cose immonde... Quindi aspetto conferme/smentite colossali da parte di qualcuno più ferrato di me.

[j18eos]

@gugo82 Non hai scritto cose immonde, è proprio l'esposizione scelta che è immonda.
Un pregio di tale esposizione è che si capisce perché si è scelto il polinomio primitivo [tex]$x^2+x+1\in\mathbb{Z}_2[x]$[/tex] anziché un altro ; i difetti che vi scorgo risiedono nel dover fare molti conti e non utilizzare la teoria dell'estensioni dei campi appieno.
Ovviamente le diverse occhiate servono: le occhiatacce truci e brutte per taluni sono occhiate bonarie e belle per altri... mi sentivo di scriverlo.

[Studente Anonimo]

Per mostrare che [tex]\{ 0,1,\alpha,\alpha+1\}[/tex] è un campo basta costruire le tabelle delle due operazioni ricordando che [tex]\alpha^2=\alpha+1[/tex]. Per esempio [tex](\alpha+1)^2=\alpha^2+2\alpha+1=\alpha+1+1=\alpha[/tex]. Oppure [tex]\alpha(\alpha+1) = \alpha^2+\alpha = \alpha+1+\alpha = 1[/tex]. Formalmente il campo con quattro elementi si può rappresentare come il quoziente [tex]\mathbb{Z}_2[X]/(x^2+x+1)[/tex], e qui [tex]\alpha = x+(x^2+x+1)[/tex] è la classe di [tex]x[/tex] nel quoziente.

"j18eos":Un pregio di tale esposizione è che si capisce perché si è scelto il polinomio primitivo [tex]$x^2+x+1\in\mathbb{Z}_2[x]$[/tex] anziché un altro

Difficile sceglierne un altro, dato che quello è l'unico polinomio irriducibile di grado 2 in [tex]\mathbb{Z}_2[X][/tex]