Radice primitiva modulo n: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 152:
dove il primo polinomio si annulla solo e solamente per i residui quadratici modulo <math>p</math> ([[Criterio di Eulero]]) e poiché le radici primitive non sono residui quadratici, il polinomio delle radici primitive deve fattorizzare il secondo polinomio. Quest'ultimo è monico e di grado <math>\tfrac{p-1}{2}=2^{2^{n}-1}</math>, cioè ha lo stesso grado del polinomo cercato: pertanto lo è.
</math> è un [[primo di Sophie Germain]] maggiore di 2, il polinomio delle radici primitive ha coefficienti di valori alternativamente <math>+1</math> e <math>-1</math>. Infatti in tal caso si ha che la cardinalità di <math>\Z_p^*</math> è <math>2q</math> e pertanto gli elementi di <math>\Z_p^*</math> possono avere ordine solo di <math>2q, q, 2, 1</math>. Per l'ordine <math>1</math> abbiamo solo l'elemento <math>+1</math> , mentre per l'ordine <math>2</math> abbiamo solo l'elemento <math>-1</math>. Gli elementi di ordine <math>2q</math> sono equinumerosi agli elementi di ordine <math>q</math>, infatti <math>\phi(2q)=\phi(q)=q-1</math>. Sia <math>h</math> un elemento di ordine <math>q</math> allora, poichè <math>q</math> è coprimo con <math>2</math> , l'elemento <math>-h</math> ha ordine pari al minimo comune multiplo tra l'ordine di <math>-1</math> (che è <math>2</math> ) e quello di <math>h</math> (che è <math>q</math> ). In sintesi per ogni elemento <math>h</math> di ordine <math>q</math> abbiamo che l'elemento <math>-h</math> ha ordine <math>2q</math>.
Sia il polinomio delle radici di ordine <math>q</math> il seguente:
<math>p_q(x)=x^{q-1}+M_{q-2}x^{q-2}...+M_2x^2+M_1x+M_0</math>
ma allora il polinomio delle radici di ordine <math>2q</math> (radici primitive) sarà:
<math>p_{2q}(x)=x^{q-1}-M_{q-2}x^{q-2}...+M_2x^2-M_1x+M_0</math>
in quanto ogni coefficiente di <math>p_{2q}(x)</math> è somma di prodotti di <math>s</math> radici opposte a quelle di <math>p_q(x)</math>, quindi il segno dipende dalla parità di <math>s</math> .
Per quanto appena affermato, proponiamoci di determinare il polinomio delle radici di ordine <math>q</math> al fine di determinare quello di ordine <math>2q</math>. Sia <math>h</math> un elemento di ordine <math>q</math> allora tutti gli altri elementi di pari ordine si esprimeranno come <math>h^i</math> con <math>(i,q)=1</math> e <math>q</math>, ricordiamo, è numero primo maggiore di <math>2</math> . Esse saranno pertanto <math>h^1, h^2, h^3, ..., h^{q-1}</math> e se ad esse aggiungiamo l'elemento <math>1</math> allora sappiamo che esse sono le radici dell'equazione <math>x^q -1 \equiv 0 \pmod{p}</math> che sappiamo fattorizzare in:
<math>x^q -1 \equiv (x-1)(x^{q-1}+x^{q-2}+...+x^2+x+1) \pmod{p}</math>
è immediato rilevare che <math>p_q(x) \equiv x^{q-1}+x^{q-2}+...+x^2+x+1 \pmod{p}</math> e per quanto detto prima otteniamo:
<math>p_{2q}(x) \equiv x^{q-1}-x^{q-2}+...+x^2-x+1 \pmod{p}</math>
che è il polinomio delle radici primitive.
==Note==
| |||