Radice primitiva modulo n: differenze tra le versioni

Versione delle 02:16, 4 ott 2014

Versione delle 02:17, 4 ott 2014

Riga 1:

In [[aritmetica modulare]], un '''generatore modulo n''' è un intero ''g'' le cui potenze '''(mod n)''' sono congruenti con i numeri [[coprimo|coprimi]] ad ''n''.

Un '''generatore''' o '''radice primitiva modulo ''n''''' è un concetto dell'[[aritmetica modulare]], in [[teoria dei numeri]]. Se ''n''≥1 è un [[numero intero|intero]], i numeri [[coprimo|coprimi]] ad ''n'', considerati modulo ''n'', costituiscono un [[gruppo (matematica)|gruppo]] rispetto all'operazione di moltiplicazione; esso viene generalmente indicato con ('''Z'''/''n'''''Z''')^× oppure '''Z'''_n^*. Esso è un [[gruppo ciclico]] se e solo se ''n'' è uguale a 2, 4, ''p''^''k'' o 2 ''p''^''k'' per un [[numero primo]] [[numero dispari|dispari]] ''p'' e ''k'' ≥ 1. Un generatore di questo gruppo ciclico è chiamato '''radice primitiva modulo ''n''''', o anche '''elemento primitivo di Z'''_n^*. In altri termini, un generatore modulo ''n'' è un intero ''g'' tale che, in modulo ''n'',

ogni intero primo con ''n'' è congruo ad una potenza di ''g''.

Riga 26:

: calcolare φ(''n''). Quindi determinare i diversi fattori primi di φ(''n''), siano ''p''₁,...,''p''_''k''. Ora, per ogni elemento ''m'' di ('''Z'''/''n'''''Z''')^×, calcolare

:<math>m^{\phi(n)/p_i}\mod n \qquad\mbox{ per } i=1,\ldots,k</math>

usando il rapido [[algoritmo]] di [[esponenziazione mediante elevamento al quadrato]]. Non appena si trova un numero ''m'' per il quale questi ''k'' risultati sono tutti diversi da 1, allora ''m'' è un generatore.

Riga 75:

Esse valgono:

* <math>\prod_{(i,p-1)=1} g^i \equiv 1 \pmod{p}</math> dove p primo diverso da 3.(Art.80, DA)

* <math>\sum_{(i,p-1)=1} g^i \equiv \mu(p-1) \pmod{p}</math> per qualsiasi p primo, <math>\mu</math> è la funzione di Möbius. Ovviamente Gauss descrisse la funzione di Möbius, che non era stata ancora formalizzata al suo tempo, in maniera equivalente. (Art.81, DA)

Se a fianco di tali funzioni simmetriche delle radici primitive, consideriamo tutte le altre (per esempio la sommatoria del prodotto delle radici primitive prese due a due etc...) allora siamo in grado di esprimere tali valori tramite funzioni polinomiali dei vari valori di <math>\mu (d)</math> e di <math>\phi(d)</math> ove d sono i divisori di p-1.

Riga 85:

Si dimostra che valgono le relazioni <math>A_i =A_{\phi(p-1)-i}</math> . Infatti se <math>y</math> è una radice primitiva allora anche <math>y^{-1}</math> la è e tali radici sono distinte per p diverso da tre. Valutando i polinomi in queste radici otteniamo:

(1) <math>y^{\phi(p-1)} +A_{n-1} y^{\phi(p-1)-1}+...+A_1 y+A_0\equiv 0 \pmod{p}</math>

(2) <math>({\tfrac{1}{y}})^{\phi(p-1)} +A_{n-1} ({\tfrac{1}{y}})^{\phi(p-1)-1}+...+A_1 ({\tfrac{1}{y}})+A_0\equiv 0 \pmod{p}</math>

moltiplicando la (2) per <math>({\tfrac{1}{y}})^{\phi(p-1)}</math> otteniamo:

(2) <math>A_0 y^{\phi(p-1)} +A_1 y^{\phi(p-1)-1}+...+A_{n-1} y+1\equiv 0 \pmod{p}</math> Sottraendo la (1) alla (2') otteniamo:

(3) <math>(A_0 -1) y^{\phi(p-1)} +(A_1 -A_{n-1}) y^{\phi(p-1)-1}+...+(A_{n-1}- A_1) y+(1- A_0)\equiv 0 \pmod{p}</math>

In particolare il termine <math>A_0</math> vale <math>(-1)^{\phi(p-1)}\prod_{(i,p-1)=1} g^i </math> dove p diverso da tre, pertanto per qualsiasi p primo e maggiore di 3 si ha che <math>\phi(p-1)</math> è pari e quindi <math>A_0 \equiv 1 \pmod{p}</math>. Sostituendo tale valore nella (3) otteniamo che l'equazione ha, quindi, grado <math>\phi(p-1)-1</math> e della quale due radici sono <math>y</math> e <math>y^{-1}</math>; considerando le altre radici primitive a due a due, l'una l'inverso dell'altra, otteniamo sempre la stessa equazione (3) e quindi, in sintesi, la (3) si annulla per tutte le <math>\phi(p-1)</math> radici primitive ed ha grado <math>\phi(p-1)-1</math> . Ma allora è identicamente nulla e quindi <math>A_i =A_{\phi(p-1)-i}</math> .

In base alle considerazioni precedenti sappiamo:

Riga 116:

Nei moduli p laddove nel polinomio si assiste ad un "passo" costante tra gli esponenti di x (per esempio per p=5 il passo degli esponenti è 2, come succede per p=13,29) e nominando k il valore di tale "passo", allora in tali moduli l'insieme delle radici primitive è quozientabile tramite il gruppo delle radici k-esime dell'unità , e vale il viceversa.

In particolare se p è un primo di Fermat allora il polinomio delle sue radici primitive sarà: <math>x^{\tfrac{p-1}{2}}+1 \equiv0 \pmod{p}</math> .

Infatti se p è un primo di Fermat esso è del tipo: <math>p=2^{2^{n}}+1</math> ed il numero delle radici primitive sarà <math>\phi(\phi(p))=\phi(p-1)=\phi(2^{2^{n}})=2^{2^{n}-1}</math> , tale sarà anche il grado del polinomio delle radici primitive. Per il Piccolo teorema di Fermat l'equazione che ha per radici tutti degli elementi di <math>Z_p ^*</math> è <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 p (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 è.

==Note==