Esercizio su campo di Galois
Il mio libro riguardo un esempio sul campo di Galois porta questo esempio che non ho ben capito:
Considerato il campo di Galois $GF(8)$ cioè $GF(2^3)$
per moltiplicare due terne,o i rispettivi polinomi,si consideri il polinomio di grado 3 $v(t)=1+t+t^3$.Esso è irriducibile su $Z_2$,poichè altrimenti avrebbe un divisore di grado uno,e quindi almeno una radice in $Z_2$.Ma ciò non si verifica in quanto $v(0)=v(1)=1$ (già questo non ho ben capito perchè lo ha fatto,lo ha fatto per vedere se si otteneva lo zero(del polinomio)?e quindi in caso si aveva zero era riducibile?è così?).Date due terne ad esempio $(0,1,1)$ e $(1,0,1)$ il loro prodotto si ottiene come segue:
$(t+t^2)(1+t^2)=t+t^2+t^3+t^4=(1+t)(1+t+t^2)+(1+t)=qv+r$
quindi il loro prodotto è:
$(0,1,1)(1,0,1)=(1,1,0)$ che è appunto il resto di sopra,ma il polinomio $v$ perchè ha scelto quello?si può scegliere un qualsiasi polinomio irriducibile?.
Si costruisca per esercizio la tavola della moltiplicazione.
Il gruppo moltiplicativo $GF(8)$ è di ordine primo( forse perchè $(1,0,0)^1=1$?lo si deduce da questo?) .Esso quindi è ciclico e ogni suo elemento diverso da 1 è un generatore.Ad esempio scegliendo $t$ si ha:
(metto i puntini al solo scopo di distanziare,così da creare meno confusione,come è sul mio libro)
$t$...............$(0,1,0)$ e questo penso di averlo capito anche per intuito,anche perchè esso proprio un elemento di $GF(8)$
$t^2$................$(0,1,0)^2=(0,0,1)$ penso anche questo di capirlo per intuito,anche esso è proprio un elemento di $GF(8)$
$t^3=1+t$.............$(0,1,0)^3=(1,1,0)$ come ci arriva ad affermare questa uguaglianza???
$t^4=t+t^2$...............$(0,1,0)^4=(0,1,1)$ idem di sopra.
$t^5=1+t+t^2$................$(0,1,0)^5=(1,1,1)$ idem di sopra
$t^6=1+t^2$.......................$(0,1,0)^6=(1,0,1)$ idem di sopra
$t^7=1$..............................$(0,1,0)^7=(1,0,0)$ idem di sopra
come ha fatto a dedurre queste uguaglianze???mi date una mano a brevissimo ho un esame ma questi procedimenti non riesco proprio a farmeli entrare in testa
Considerato il campo di Galois $GF(8)$ cioè $GF(2^3)$
per moltiplicare due terne,o i rispettivi polinomi,si consideri il polinomio di grado 3 $v(t)=1+t+t^3$.Esso è irriducibile su $Z_2$,poichè altrimenti avrebbe un divisore di grado uno,e quindi almeno una radice in $Z_2$.Ma ciò non si verifica in quanto $v(0)=v(1)=1$ (già questo non ho ben capito perchè lo ha fatto,lo ha fatto per vedere se si otteneva lo zero(del polinomio)?e quindi in caso si aveva zero era riducibile?è così?).Date due terne ad esempio $(0,1,1)$ e $(1,0,1)$ il loro prodotto si ottiene come segue:
$(t+t^2)(1+t^2)=t+t^2+t^3+t^4=(1+t)(1+t+t^2)+(1+t)=qv+r$
quindi il loro prodotto è:
$(0,1,1)(1,0,1)=(1,1,0)$ che è appunto il resto di sopra,ma il polinomio $v$ perchè ha scelto quello?si può scegliere un qualsiasi polinomio irriducibile?.
Si costruisca per esercizio la tavola della moltiplicazione.
Il gruppo moltiplicativo $GF(8)$ è di ordine primo( forse perchè $(1,0,0)^1=1$?lo si deduce da questo?) .Esso quindi è ciclico e ogni suo elemento diverso da 1 è un generatore.Ad esempio scegliendo $t$ si ha:
(metto i puntini al solo scopo di distanziare,così da creare meno confusione,come è sul mio libro)
$t$...............$(0,1,0)$ e questo penso di averlo capito anche per intuito,anche perchè esso proprio un elemento di $GF(8)$
$t^2$................$(0,1,0)^2=(0,0,1)$ penso anche questo di capirlo per intuito,anche esso è proprio un elemento di $GF(8)$
$t^3=1+t$.............$(0,1,0)^3=(1,1,0)$ come ci arriva ad affermare questa uguaglianza???
$t^4=t+t^2$...............$(0,1,0)^4=(0,1,1)$ idem di sopra.
$t^5=1+t+t^2$................$(0,1,0)^5=(1,1,1)$ idem di sopra
$t^6=1+t^2$.......................$(0,1,0)^6=(1,0,1)$ idem di sopra
$t^7=1$..............................$(0,1,0)^7=(1,0,0)$ idem di sopra
come ha fatto a dedurre queste uguaglianze???mi date una mano a brevissimo ho un esame ma questi procedimenti non riesco proprio a farmeli entrare in testa
Risposte
[mod="cirasa"]Per cortesia, fai attenzione alla sezione.
Sposto in Algebra.[/mod]
Sposto in Algebra.[/mod]
"zipangulu":
Il gruppo moltiplicativo $GF(8)$ è di ordine primo( forse perchè $(1,0,0)^1=1$?lo si deduce da questo?) .Esso quindi è ciclico e ogni suo elemento diverso da 1 è un generatore.
Il campo di Galois [tex]\text{GF}(8)[/tex] ha ordine, appunto, [tex]8[/tex]. Il suo gruppo moltiplicativo è l'insieme dei suoi elementi invertibili; siccome siamo in un campo, questi non è altro che l'insieme degli elementi diversi da [tex]0[/tex]. Ora, [tex]8-1 = 7[/tex] e [tex]7[/tex] è un numero primo.
Tuttavia, ti faccio osservare che non è il caso di "faticare" così tanto (anche se in questo caso in realtà la fatica è minima): si sa che ogni gruppo finito contenuto in un campo è ciclico, e tanto basta per concludere.
Poi, [tex]\text{GF}(8)[/tex] è ottenuto come campo di spezzamento su [tex]\mathbb{F}_2 := \mathbb{Z}/2\mathbb{Z}[/tex] di un (qualsiasi) polinomio irriducibile di grado [tex]3[/tex]. Ora, [tex]x^3+x+1[/tex] è irriducibile (essendo di terzo grado, è irriducibile se e solo se non ha radici nel campo e questa è una banale verifica). Pertanto [tex]\text{GF}(8) \simeq \mathbb{F}_2[x] / (x^3+x+1)[/tex].
Questo chiarisce i tuoi dubbi, oppure comunque non ti rimane chiaro come si svolgono le operazioni?
Nota: Il polinomio di terzo grado irriducibile scelto non è tanto importante, tanto sappiamo che tutti i campi finiti con la stessa cardinalità sono isomorfi!
Il campo di Galois $GF(8)$ ha ordine, appunto,$8$.
ma non avevamo detto fosse del primo ordine?
Questo chiarisce i tuoi dubbi, oppure comunque non ti rimane chiaro come si svolgono le operazioni?
Perdonami ma sono alle prime armi,noto sicuramente che sei preparatissimo,ma ancora non ho ben capito come sia arrivato a determinare quelle uguaglianze,ad esempio:
perchè
$t^4=t+t^2$.........$(0,1,0)^4=(0,1,1)$
secondo quale procedimento ci arriva ad affermarlo?mi potresti spiegare in parole semplici il procedimento (anche magari nella pratica,con la pratica è sempre + facile capire) da seguire?
Per te ordine cosa significa? Per me significa semplicemente cardinalità...
Per quanto riguarda le operazioni, non c'è nulla di più facile. Siccome stiamo lavorando nel quoziente [tex]\mathbb{F}_2[x]/(x^3+x+1)[/tex] allora ogni elemento si scriverà come [tex]a_0 + a_1 x + a_2 x^2[/tex] con [tex]a_i \in \mathbb{F}_2[/tex] ([tex]i = 0, 1, 2[/tex]). Pertanto identifichiamo una simile scrittura con [tex](a_0,a_1,a_2)[/tex].
Ora, ad esempio calcoliamo [tex]x^4 = (0,1,0)^4[/tex]. Basta dividere [tex]x^4[/tex] per [tex]x^3 + x + 1[/tex] in [tex]\mathbb{F}_2[x][/tex]. Semplici conti ti mostreranno che [tex]x^4 = x\cdot (x^3 + x + 1) - x^2 - x[/tex]. Ma [tex]-1 \equiv 1 \pmod{2}[/tex] e quindi [tex]x^4 = x+ x^2 + (x^3 + x +1)[/tex] (indico con questa scrittura il laterale del polinomio [tex]x^2 + x[/tex]). Quindi [tex](0,1,0)^4 = (0,1,1)[/tex].
Ti è più chiaro adesso?
Per quanto riguarda le operazioni, non c'è nulla di più facile. Siccome stiamo lavorando nel quoziente [tex]\mathbb{F}_2[x]/(x^3+x+1)[/tex] allora ogni elemento si scriverà come [tex]a_0 + a_1 x + a_2 x^2[/tex] con [tex]a_i \in \mathbb{F}_2[/tex] ([tex]i = 0, 1, 2[/tex]). Pertanto identifichiamo una simile scrittura con [tex](a_0,a_1,a_2)[/tex].
Ora, ad esempio calcoliamo [tex]x^4 = (0,1,0)^4[/tex]. Basta dividere [tex]x^4[/tex] per [tex]x^3 + x + 1[/tex] in [tex]\mathbb{F}_2[x][/tex]. Semplici conti ti mostreranno che [tex]x^4 = x\cdot (x^3 + x + 1) - x^2 - x[/tex]. Ma [tex]-1 \equiv 1 \pmod{2}[/tex] e quindi [tex]x^4 = x+ x^2 + (x^3 + x +1)[/tex] (indico con questa scrittura il laterale del polinomio [tex]x^2 + x[/tex]). Quindi [tex](0,1,0)^4 = (0,1,1)[/tex].
Ti è più chiaro adesso?
l'unica cosa poco chiara è "laterale del polinomio"
cioè avendo
$-1-=1 (mod 2) -> -2=alpha2$
segue che
$1-=-1 (mod2) -> 2=alpha'2$ dove $alpha'=-alpha$
penso intendessi questo in linea di massima,comunque grazie 1000!
cioè avendo
$-1-=1 (mod 2) -> -2=alpha2$
segue che
$1-=-1 (mod2) -> 2=alpha'2$ dove $alpha'=-alpha$
penso intendessi questo in linea di massima,comunque grazie 1000!
"laterale" è solo un modo abbreviato per dire: "classe di equivalenza del polinomio [tex]x^2+x[/tex] nell'anello quoziente [tex]\mathbb{F}_2[x]/(x^3+x+1)[/tex]".
Per quanto riguarda quello che segue, non capisco che cosa tu intenda. Volevo solo dire che, essendo in caratteristica [tex]2[/tex], scrivere [tex]1[/tex] o scrivere [tex]-1[/tex] non fa alcuna differenza!
Per quanto riguarda quello che segue, non capisco che cosa tu intenda. Volevo solo dire che, essendo in caratteristica [tex]2[/tex], scrivere [tex]1[/tex] o scrivere [tex]-1[/tex] non fa alcuna differenza!
ok perfetto!
un'ultima domanda;ho questo esercizio:
Dopo aver verificato (motivando la risposta)che il polinomio $v(t)=t^4+t^3+1$ $in$ $Z_2[t]$ è irriducibile su $Z_2$,calcolare il periodo di $(0,1,0,1)$ in $GF(2^4)$.
Puoi dirmi se in linea di massima ho ragionato bene?
io ho ragionato così:
poichè l'insieme $Z_2$ cioè l'insieme dei possibili resti delle divisione per 2,è così costituito $Z_2={0,1}$
affinchè $v(t)$ sia irriducibile su $Z_2$,in esso non vi deve essere alcuna radice del polinomio $v(t)$ e poichè
$v(0)=v(1)=1$ affermo che il polinomio è irriducibile su $Z_2$
Ora per calcolare il periodo di $(0,1,0,1)$ penso(magari mi sbaglio) che dovrei trovare un elemento generatore,come ad esempio $t$ quindi $(0,1,0,0)$ e calcolando le varie $t^i$ con $i in {1,...,15}$ e contare quante volte appare come "risultato".
E' corretto?
un'ultima domanda;ho questo esercizio:
Dopo aver verificato (motivando la risposta)che il polinomio $v(t)=t^4+t^3+1$ $in$ $Z_2[t]$ è irriducibile su $Z_2$,calcolare il periodo di $(0,1,0,1)$ in $GF(2^4)$.
Puoi dirmi se in linea di massima ho ragionato bene?
io ho ragionato così:
poichè l'insieme $Z_2$ cioè l'insieme dei possibili resti delle divisione per 2,è così costituito $Z_2={0,1}$
affinchè $v(t)$ sia irriducibile su $Z_2$,in esso non vi deve essere alcuna radice del polinomio $v(t)$ e poichè
$v(0)=v(1)=1$ affermo che il polinomio è irriducibile su $Z_2$
Ora per calcolare il periodo di $(0,1,0,1)$ penso(magari mi sbaglio) che dovrei trovare un elemento generatore,come ad esempio $t$ quindi $(0,1,0,0)$ e calcolando le varie $t^i$ con $i in {1,...,15}$ e contare quante volte appare come "risultato".
E' corretto?
No, in toto.
1) in generale, per mostrare che un polinomio è irriducibile su un campo assegnato, non è sufficiente mostrare che non ha radici nel campo. Ad esempio [tex]x^4 + 2 x^2 + 1 = (x^2 + 1)^2[/tex] non ha radici in [tex]\mathbb{R}[/tex], eppure è irriducibile. Prima funzionava perché il grado era [tex]3[/tex], ma da [tex]4[/tex] in su non è più un criterio valido. Non c'è speranza, dovrai mostrare che è impossibile scrivere [tex]t^4 + t^3 +1 = (t^2 + a t + b) (t^2 + ct + d)[/tex] (con un po' di conti e il principio di identità dei polinomi dovresti riuscirci).
2) Per calcolare il periodo, non serve avere un generatore. Semplicemente computa le potenze successive di [tex](0,1,0,1)[/tex] con il metodo di prima fino a quando non trovi [tex](1,0,0,0)[/tex] (l'elemento neutro).
1) in generale, per mostrare che un polinomio è irriducibile su un campo assegnato, non è sufficiente mostrare che non ha radici nel campo. Ad esempio [tex]x^4 + 2 x^2 + 1 = (x^2 + 1)^2[/tex] non ha radici in [tex]\mathbb{R}[/tex], eppure è irriducibile. Prima funzionava perché il grado era [tex]3[/tex], ma da [tex]4[/tex] in su non è più un criterio valido. Non c'è speranza, dovrai mostrare che è impossibile scrivere [tex]t^4 + t^3 +1 = (t^2 + a t + b) (t^2 + ct + d)[/tex] (con un po' di conti e il principio di identità dei polinomi dovresti riuscirci).
2) Per calcolare il periodo, non serve avere un generatore. Semplicemente computa le potenze successive di [tex](0,1,0,1)[/tex] con il metodo di prima fino a quando non trovi [tex](1,0,0,0)[/tex] (l'elemento neutro).
capito tutto,grazie mille!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo