Radice primitiva modulo n: differenze tra le versioni

Versione delle 02:47, 5 ott 2014

Versione delle 08:59, 5 ott 2014

Riga 150:

:<math>x^{p-1}-1\equiv(x^{\tfrac{p-1}{2}}-1)(x^{\tfrac{p-1}{2}}+1) \equiv 0 \pmod{p},</math>

dove il primo polinomio si annulla solo e solamente per i residui quadratici modulo <math>p</math> ([[Criteriocriterio 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 è.

Se <math>p</math> è un [[numero primo sicuro]] maggiore di <math>5</math>, ossia se <math>p=2q+1</math> dove <math>q</math> è un [[primo di Sophie Germain]] maggiore di <math>2</math>, 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è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>.

Se p è un [[numero primo sicuro]] maggiore di 5, ossia se <math>p=2q+1</math> dove <math>q

</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}...\ldots+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}...\ldots+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, ...\ldots, 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)0 \pmod{p},</math>

che sappiamo fattorizzare in:

è 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)^q -1 \equiv (x-1)(x^{q-1}-+x^{q-2}+...\ldots+x^2-+x+1) \pmod{p},</math>

è immediato rilevare che

è immediato rilevare che :<math>p_q(x) \equiv x^{q-1}+x^{q-2}+...\ldots+x^2+x+1 \pmod{p},</math> e per quanto detto prima otteniamo:

e per quanto detto prima otteniamo:

<math>p_{2q}(x) \equiv x^{q-1}-x^{q-2}+\ldots+x^2-x+1 \pmod{p},</math>

che è il polinomio delle radici primitive.