Generatore di GF(9)*
Considerato GF(9), determinare un generatore del suo gruppo moltiplicativo.
Ora, finche l'ordine del gruppo moltiplicativo è primo, allora qualsiasi elemento scelga è un generatore, cioè il gruppo è ciclico. Ma nel caso in cui l'ordine non è primo, come in questo caso (l'ordine è 3^2 - 1 = 8), come faccio a determinare un generatore?
Ora, finche l'ordine del gruppo moltiplicativo è primo, allora qualsiasi elemento scelga è un generatore, cioè il gruppo è ciclico. Ma nel caso in cui l'ordine non è primo, come in questo caso (l'ordine è 3^2 - 1 = 8), come faccio a determinare un generatore?
Risposte
Guarda che c'è un teorema che te li individua tutti, conseguenza del teorema di Bezout se non erro!
Senza determinare prima un polinomio v(t) irriducibile su $ ZZ $ 3 ? Io avevo pensato di trovare un polinomio del genere e poi procedere alla solita maniera. Cioè determinare un elemento di ($ ZZ $ 3)^2 di periodo 8. Ovviamente tenendo conto del resto nella divisione per v(t). Ma il processo è molto lungo.
Non ricordo il teorema che dici tu, scusami. In cosa consiste? Che algoritmo utilizza?
Non ricordo il teorema che dici tu, scusami. In cosa consiste? Che algoritmo utilizza?
Se ho capito bene, quello che dice Armando (che saluto 
) è questo: tu sai che quel gruppo che stai cercando è ciclico di ordine 8, cioè è $C_8$, perchè il gruppo moltiplicativo di un campo finito è ciclico.
Pensa per un attimo a $ZZ_8$: qua dentro, i conti li sappiamo fare bene: per Bezout, i generatori sono tutti e soli gli elementi coprimi con 8 (le classi rappresentate da 1,3,5,7). Se riesci a beccare un isomorfismo tra il tuo gruppo moltiplicativo e questo gruppo additivo (che è un po' il "modello": converrai con me che è l'unico gruppo ciclico di ordine 8 a meno di isomorfismi), sei a posto.
Francamente, comunque, non so quanto questa strada sia percorribile e scevra da conti.
) è questo: tu sai che quel gruppo che stai cercando è ciclico di ordine 8, cioè è $C_8$, perchè il gruppo moltiplicativo di un campo finito è ciclico. Pensa per un attimo a $ZZ_8$: qua dentro, i conti li sappiamo fare bene: per Bezout, i generatori sono tutti e soli gli elementi coprimi con 8 (le classi rappresentate da 1,3,5,7). Se riesci a beccare un isomorfismo tra il tuo gruppo moltiplicativo e questo gruppo additivo (che è un po' il "modello": converrai con me che è l'unico gruppo ciclico di ordine 8 a meno di isomorfismi), sei a posto.
Francamente, comunque, non so quanto questa strada sia percorribile e scevra da conti.
Ok. Ho capito! 
Ma nel momento in cui devo calcolare un generatore di GF(9)* (il gruppo moltiplicativo di GF(9) per intenderci) dovrò lo stesso determinare un polinomio irriducibile su Z3. Cioè da quello che ho capito i campi che si ottengono sono isomorfi per le diverse scelte di tale polinomio. Giusto? 
Ma come dovrò considerare gli elementi fra loro coprimi? A cosa mi servono?
Ma nel momento in cui devo calcolare un generatore di GF(9)* (il gruppo moltiplicativo di GF(9) per intenderci) dovrò lo stesso determinare un polinomio irriducibile su Z3. Cioè da quello che ho capito i campi che si ottengono sono isomorfi per le diverse scelte di tale polinomio. Giusto? Ma come dovrò considerare gli elementi fra loro coprimi? A cosa mi servono?
@Alfonso A meno di isomorfismi vi è un unico campo finito di ordine \(p^n\) ottenibile dal campo fondamentale \(\mathbb{Z}_p\) come campo di spezzamento di un polinomio di grado \(n\) irriducibile su \(\mathbb{Z}_p\)!
Penso che ciò dissolva alcuni tuoi dubbi.
Sai continuare da solo?
@Paolo Grazie dei saluti!
Penso che ciò dissolva alcuni tuoi dubbi.
Sai continuare da solo?
@Paolo Grazie dei saluti!
Ok, Ok! Fin qui ci sono, grazie! Forse mi sono spiegato male io. Intendo dire: scelto il polinomio irriducibile su Zp, come faccio a determinare un generatore del gruppo moltiplicativo di GF(p^n)? Se il gruppo moltiplicativo è di ordine primo allora va bene: qualsiasi elemento di (Zp)^n scelgo (ovviamente diverso dall'unità) esso è un generatore. Ma nel caso in cui l'ordine del gruppo moltiplicativo di GF(p^n) non sia primo (come nell'esempio che ho fatto: GF(9), il suo gruppo moltiplicativo avrà ordine 8 e dunque non è primo) un elemento del genere come lo determino? Devo necessariamente calcolarmi tutte le potenze di ogni elemento fino a trovarne una che abbia come periodo 8? O esiste un metodo particolare?
Scusate l'insistenza!
Scusate l'insistenza!
"Paolo90":Per essere più esplicito: essendo a meno di isomorfismi \(GF(9)*\) niente altri che \(\mathbb{Z}_8\), scegli...
...i generatori sono tutti e soli gli elementi coprimi con 8 (le classi rappresentate da 1,3,5,7)...
Va bene... ma finchè si tratta di soli numeri ci sono. Ho capito. In questo caso ho coppie ordinate di elementi di Z3! Come faccio a scegliere un coprimo con 8??? 
Sia $\mathbb{F}_3$ il campo con tre elementi. Vogliamo costruire $\mathbb{F}_9$ il campo con nove elementi.
A tal fine, basterà trovare un polinomio di secondo grado, $p(x)$ irriducibile in $\mathbb{F}_3[x]$, in modo tale da realizzare il nostro $\mathbb{F}_9$ come campo di spezzamento di $p(x)$ su $\mathbb{F}_3[x]$.
Ok fin qui? Ora $p(x)$ lo possiamo tranquillamente cercare della forma $x^2-a$, per un opportuno $a \in \mathbb{F}_3$ (per via di un noto fatto sul sottogruppo dei quadrati in un campo finito... in soldoni, tolto $\mathbb{F}_2$, in ogni campo finito la funzione $x \mapsto x^2$ non è iniettiva, perchè $(-1)^2=(1)^2$ e però $1 \ne -1$, e quindi nemmeno suriettiva).
Va be', insomma, non è difficile convincerci che $2$ non è un quadrato in $\mathbb{F}_3$, quindi $p(x)=x^2-2$ va bene. A questo punto, se chiamo la classe di $x$ nel quoziente $\overline{x}=\alpha$, ottengo
$\mathbb{F}_9 = (\mathbb{F}_3[x])/ ((x^2-2))={0,1,2,alpha, alpha+1, alpha+2, 2alpha, 2alpha+1, 2alpha+2}$
Ecco il nostro campo con nove elementi. Ora dovrebbe essere chiaro come finire: il gruppo moltiplicativo $G$ di $\mathbb{F}_9$ è ovviamente $\mathbb{F}_9 setminus {0}$; ti lascio da verificare che la mappa $\psi: G \to C_8$, definita in maniera "ovvia", ti dà un isomorfismo di tale gruppo in $C_8$ (additivo). Da tale isomorfismo leggi i generatori che cerchi.
Spero sia chiaro
A tal fine, basterà trovare un polinomio di secondo grado, $p(x)$ irriducibile in $\mathbb{F}_3[x]$, in modo tale da realizzare il nostro $\mathbb{F}_9$ come campo di spezzamento di $p(x)$ su $\mathbb{F}_3[x]$.
Ok fin qui? Ora $p(x)$ lo possiamo tranquillamente cercare della forma $x^2-a$, per un opportuno $a \in \mathbb{F}_3$ (per via di un noto fatto sul sottogruppo dei quadrati in un campo finito... in soldoni, tolto $\mathbb{F}_2$, in ogni campo finito la funzione $x \mapsto x^2$ non è iniettiva, perchè $(-1)^2=(1)^2$ e però $1 \ne -1$, e quindi nemmeno suriettiva).
Va be', insomma, non è difficile convincerci che $2$ non è un quadrato in $\mathbb{F}_3$, quindi $p(x)=x^2-2$ va bene. A questo punto, se chiamo la classe di $x$ nel quoziente $\overline{x}=\alpha$, ottengo
$\mathbb{F}_9 = (\mathbb{F}_3[x])/ ((x^2-2))={0,1,2,alpha, alpha+1, alpha+2, 2alpha, 2alpha+1, 2alpha+2}$
Ecco il nostro campo con nove elementi. Ora dovrebbe essere chiaro come finire: il gruppo moltiplicativo $G$ di $\mathbb{F}_9$ è ovviamente $\mathbb{F}_9 setminus {0}$; ti lascio da verificare che la mappa $\psi: G \to C_8$, definita in maniera "ovvia", ti dà un isomorfismo di tale gruppo in $C_8$ (additivo). Da tale isomorfismo leggi i generatori che cerchi.
Spero sia chiaro
Ho capito. In pratica dunque posso soltanto determinare il numero (quanti sono) i generatori che cerco, ma non identificarli! Giusto?
"Paolo90":
[...] ti lascio da verificare che la mappa $\psi: G \to C_8$, definita in maniera "ovvia", ti dà un isomorfismo di tale gruppo in $C_8$ (additivo).
Mah... mi sa che mi devo ricredere, pensavo fosse piuttosto scontata la definizione dell'isomorfismo, invece ho faticato un po' per scriverlo esplicitamente. Forse mi sono perso qualcosa, boh... Alla luce dei miei conti è abbastanza inutile il ragionamento che suggeriva Armando, facendo il parallelo con $C_8$. Uno fa i conti in quel gruppo e fine. Cerchi gli elementi di periodo massimo e hai i tuoi generatori.
"Alfonso89":
Ho capito. In pratica dunque posso soltanto determinare il numero (quanti sono) i generatori che cerco, ma non identificarli! Giusto?
Sì, certo, puoi determinarne facilmente il numero. Per trovarli invece ho faticato un po' di più, ma salvo errori, dovrebbero essere $alpha+1,alpha+2,2alpha+1,2alpha+2$.
Ok Ok Capito! 
Dunque i conti vanno fatti ugualmente quando il gruppo moltiplicativo non è di ordine primo... cioè non è possibile stabilire a priori quali siano i generatori di tale gruppo. La ricerca dei generatori presuppone obbligatoriamente il calcolo dell'ordine di ogni elemento. Giusto? (In effetti dipende anche dalla scelta del polinomio irriducibile!)
Dunque i conti vanno fatti ugualmente quando il gruppo moltiplicativo non è di ordine primo... cioè non è possibile stabilire a priori quali siano i generatori di tale gruppo. La ricerca dei generatori presuppone obbligatoriamente il calcolo dell'ordine di ogni elemento. Giusto? (In effetti dipende anche dalla scelta del polinomio irriducibile!)
"Paolo90":
[quote="Paolo90"][...] ti lascio da verificare che la mappa $\psi: G \to C_8$, definita in maniera "ovvia", ti dà un isomorfismo di tale gruppo in $C_8$ (additivo).
Mah... mi sa che mi devo ricredere, pensavo fosse piuttosto scontata la definizione dell'isomorfismo, invece ho faticato un po' per scriverlo esplicitamente. Forse mi sono perso qualcosa, boh... Alla luce dei miei conti è abbastanza inutile il ragionamento che suggeriva Armando, facendo il parallelo con $C_8$...[/quote] Beh, si inizia col notare che \(\alpha^2=2;\,2^2=1\) quindi \(o(\alpha)=4;\,o(2)=2; o(1)=1\) e gli altri elementi sono generatori; dato che per i gruppi ciclici (finiti) \(\mathbb{Z}_m\) vale il teorema inverso forte di Lagrange, ovvero per ogni divisore \(d\) di \(m\) esiste un'unico sottogruppo (ciclico) di ordine \(d\)!
Per essere completamente esplicito: \(\langle\alpha\rangle=\{1;2;\alpha;2\alpha\}\) quindi i generatori ricercati sono \(\alpha+1;\alpha+2;2\alpha+1;2\alpha+2\).
"Alfonso89":Sì!
...Giusto?...
"Alfonso89":I calcoli sì, il campo che si ottiene no!
...(In effetti dipende anche dalla scelta del polinomio irriducibile!)
"Alfonso89":
Ok Ok Capito!
E sì, in questo caso sì. Ripeto quanto dicevo sopra: se riuscissimo a beccare subito l'isomorfismo con il ciclico corrispondente, saremmo a posto, lì i conti li sappiamo fare benissimo. Forse Armando potrà fare maggiore chiarezza su questo punto.
"Alfonso89":
La ricerca dei generatori presuppone obbligatoriamente il calcolo dell'ordine di ogni elemento. Giusto?
Sì, anche se ci sono un paio di trucchetti standard. Ad esempio, in questo caso, basta calcolare le prime 4 potenze di ogni elemento. Infatti, se non hai ma trovato l'unità nelle prime quattro potenze di un elemento, allora concludi subito che quell'elemento è un generatore. Ti invito a riflettere sul perché e a generalizzare questo risultato (ad un gruppo ciclico di ordine $n$ qualsiasi). La parola magica è Lagrange.
"Alfonso89":
(In effetti dipende anche dalla scelta del polinomio irriducibile!)
Sì, per i conti sì, dipende dal polinomio che scegli. Tieni conto, comunque, che i campi che ottieni - e di conseguenza i loro gruppi moltiplicativi - sono in sostanza lo stesso, o per meglio dire, sono isomorfi.
EDIT: ok, l'intervento di Armando risolve la questione. Grazie.
OKEY Superchiarissimissimo!! 
Meglio di così non esiste!! Vi ho stressato forse anche troppo!
Vi ringrazio ancora!!
Meglio di così non esiste!! Vi ho stressato forse anche troppo! Vi ringrazio ancora!!
Prego Paolo; mi spiace per i conti in eccesso!
Alfonso, non sò ma ho l'impressione che i campi finiti non ti siano andati giù;
forse è meglio che tu faccia esercizi solo sui campi di spezzamento di polinomi assegnati, per poi procedere con altra tipologia di esercizi!
Personalmente non mi sono stressato, raramente faccio questi esercizi; non vorrei arruginirmi!
Alfonso, non sò ma ho l'impressione che i campi finiti non ti siano andati giù;
forse è meglio che tu faccia esercizi solo sui campi di spezzamento di polinomi assegnati, per poi procedere con altra tipologia di esercizi! Personalmente non mi sono stressato, raramente faccio questi esercizi; non vorrei arruginirmi!
"j18eos":
Alfonso, non sò ma ho l'impressione che i campi finiti non ti siano andati giù;
Ahah! In effetti sì.. sono ancora alle prime armi sull'argomento
Accetto il consiglio! "j18eos":
Personalmente non mi sono stressato, raramente faccio questi esercizi; non vorrei arruginirmi!
Mi fa piacere! Ogni tanto un po di svitol serve!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo