Radice primitiva modulo n: differenze tra le versioni

Versione delle 02:47, 5 ott 2014

Versione attuale delle 16:19, 17 giu 2023

(32 versioni intermedie di 15 utenti non mostrate)

Riga 1:

In [[matematica]], in particolare in [[aritmetica modulare]], ununa '''generatoreradice primitiva modulo <math>n</math>''' o '''radice primitivageneratore modulo <math>n</math>''' (o semplicemente '''generatore''' se è chiaro il contesto,) è un [[Numeronumero intero|intero]] <math>g</math> le cui potenze [[Aritmetica modulare|modulo]] <math>n</math> sono congruenti con i numeri [[coprimo|coprimi]] ad <math>n</math>.

Se <math>n\ge 1</math> è un [[Numero intero|intero]], i numeri [[coprimo|coprimi]] ad <math>n</math>, considerati modulo <math>n</math>, costituiscono un [[Gruppo (matematica)|gruppo]] rispetto all'operazione di moltiplicazione; esso viene generalmente indicato con <math>(\Z/n\Z)^*</math> oppure <math>\Z_n^*</math>. Esso è un [[gruppo ciclico]] se e solo se <math>n</math> è uguale a <math>2</math>, <math>4</math>, <math>p^k</math> o <math>2p^k</math> per un [[numero primo]] [[Numero dispari|dispari]] <math>p</math> e <math>k\ge 1</math>. Un generatore di questo gruppo ciclico è chiamato anche '''elemento primitivo di <math>\Z_n^*</math>'''.

I generatori modulo <math>n</math> rivestono un'importanza considerevole in [[crittografia]].

Se <math>n\ge 1</math> è un [[Numero intero|intero]], i numeri [[coprimo|coprimi]] ad <math>n</math>, considerati modulo <math>n</math>, costituiscono un [[Gruppo (matematica)|gruppo]] rispetto all'operazione di moltiplicazione; esso viene generalmente indicato con <math>(\Z/n\Z)^*</math> oppure <math>\Z_n^*</math>. Esso è un [[gruppo ciclico]] se e solo se <math>n</math> è uguale a <math>2</math>, <math>4</math>, <math>p^k</math> o <math>2p^k</math> per un [[numero primo]] [[Numero dispari|dispari]] <math>p</math> e <math>k\ge 1</math>. Un generatore di questo gruppo ciclico è chiamato anche '''elemento primitivo di <math>\Z_n^*</math>.

Si consideri per esempio <math>n=14</math>. Gli elementi di

Riga 9 ⟶ 7:

:<math>(\Z/14\Z)^*,</math>

sono le classi di congruenza di <math>1</math>, <math>3</math>, <math>5</math>, <math>9</math>, <math>11</math> e <math>13</math>. che sono [[coprimo|coprimi]] con <math>n = 14.</math>

Si ha che <math>3</math> è un generatore modulo <math>14</math>, perché 3² mod 14 = 9, 3³ mod 14 = 13, 3⁴ mod 14 = 11, 3⁵ mod 14 = 5 e 3⁶ =mod 114 (modulo= 14)1. L'unica altra radice primitiva modulo <math>14</math> è <math>5</math>.

I generatori modulo <math>n</math> rivestono un'importanza considerevole in [[crittografia]].

==Trovare i generatori==

Di seguito vi è una tabella che contiene i più piccoli generatori per diversi valori di <math>n</math><ref>{{OEIS|A046145}}</ref>:

{| class="wikitable"

Riga 38 ⟶ 37:

*se l'[[ipotesi di Riemann generalizzata]] è vera, allora, per ogni numero primo <math>p</math>, esiste un generatore modulo <math>p</math> minore di <math>70\ln^2 p</math>.

== Dimostrazione dell'esistenza di un generatore modulo ''p''^k, ''p'' dispari ==

La dimostrazione dell'esistenza del generatore procede dapprima provando che essa esiste per ogni numero primo <math>p</math>, poi dimostrando che, se <math>a</math> è una radice primitiva di <math>p</math>, allora o <math>a</math> o <math>p+a</math> è una radice primitiva di <math>p^2</math>, e che questa è poi radice primitiva anche di ogni potenza successiva di <math>p</math>. Infatti, sia <math>a</math> una radice primitiva modulo <math>p</math>. Allora, per definizione di radice primitiva

Riga 54 ⟶ 52:

:<math>a^{\phi(p^{k-2})}\equiv 1 \mod p^{k-2},</math>

ossia

ovvero

:<math>a^{\phi(p^{k-2})}=1+lp^{k-2},</math>

per un qualche <math>l</math><math></math>. Questa relazione vale anche modulo <math>p^k</math>; inoltre l'ordine di <math>a</math> modulo <math>p^k</math> deve essere un multiplo di <math>\phi(p^{k-1})</math>, perché ha quest'ordine modulo <math>p^{k-1}</math>. Quindi, poiché <math>\phi(p^k)=p\phi(p^{k-1})</math>, l'ordine può essere solo <math>\phi(p^{k-1})</math> o <math>p\phi(p^{k-1})</math>; in particolare, <math>a</math> è una radice primitiva se il suo ordine è il secondo di questi valori. Se <math>p</math> è un primo dispari

:<math>a^{\phi(p^{k-1})}=(a^{\phi(p^{k-2})})^p=(1+lp^{k-2})^p\equiv 1+\binom{p}{p-1}lp^{k-2}\mod p^k\equiv 1+lp^{k-1}\mod p^k.</math>

Riga 68 ⟶ 66:

contro l'ipotesi che l'ordine di <math>a</math> modulo <math>p^{k-1}</math> sia <math>\phi(p^{k-1})</math>. Questo è assurdo, e quindi l'ordine di <math>a</math> modulo <math>p^k</math> è esattamente <math>\phi(p^k)</math>, e <math>a</math> è una radice primitiva modulo <math>p^k</math>. Per induzione questo è valido per ogni <math>k</math>.

L'estensione ai numeri nella forma <math>2p^k</math> segue immediatamente, perché il gruppo moltiplicativo di questo anello contiene lo stesso numero di elementi di quello dell'anello di <math>p^k</math> elementi, ed esiste una [[corrispondenza biunivoca]] che conserva le operazioni (ossia un [[isomorfismo]]) tra questi due gruppi.

== Funzioni simmetriche delle radici primitive modulo p ==

Indicando con <math>g</math> il generatore di <math>\Z_p^*</math> allora, per quanto precedentemente esposto, tutte le radici primitive modulo <math>p</math> si potranno esprimere come <math>g^i</math> dove <math>(i,\phi(p))=(i,p-1)=1.</math> .

Indicando con <math>g</math> il generatore di <math>\Z_p^*</math> allora, per quanto precedentemente esposto, tutte le radici primitive modulo <math>p</math> si potranno esprimere come <math>g^i</math> dove <math>(i,\phi(p))=(i,p-1)=1</math> .

Gauss nelle Disquisitiones Arithmeticae dimostrò agli articoli 80 ed 81 il valore (modulo <math>p</math> primo) della somma delle radici primitive di <math>\Z_p</math> e del loro prodotto.

Riga 95 ⟶ 92:

:<math>\sum_{(i,p-1)=1} (g^i)^k=\tfrac{\phi(p-1)}{\phi\left(\tfrac{p-1}{k}\right)}\mu(\tfrac{p-1}{k}).</math>

Sia ora <math>k</math> dove <math>(k,p-1)=b</math>, quindi <math>k=ab</math> e <math>(a,p-1)=1</math> pertanto al posto di applicare direttamente la potenza <math>k</math> alle radici primitive, prima applichiamo la potenza <math>a</math> e poi, agli elementi ottenuti, la potenza <math>b</math>. La potenza <math>a</math> manda le radici primitive in sé stesse, la potenza <math>b</math> le fa "restringere" in un sottoordinesottordine e pertanto, indicando <math>(k,p-1)</math> in luogo di <math>b</math> otteniamo:

:<math>\sum_{(i,p-1)=1} (g^i)^k=\tfrac{\phi(p-1)}{\phi\left(\tfrac{p-1}{(k,p-1)}\right)}\mu(\tfrac{p-1}{(k,p-1)}).</math>

Tali formule si rivelano utili per calcolare le varie funzioni simmetriche delle radici primitive, tramite i [[teoremi newtoniani]] riusciamo facilmente nell'impresa. Supponiamo di voler calcolare il valore della sommatoria del prodotto delle radici primitive prese due a due, allora tramite i teoremi newtoniani otteniamo che:

:<math>\sum_{(ij,p-1)=1;i \ne j} g^ig^j \equiv \tfrac{1}{2}[(\sum_{(i,p-1)=1} g^i )^2-\sum_{(i,p-1)=1} (g^i)^2]\equiv \tfrac{1}{2}[(\mu(p-1))^2-\mu(\tfrac{p-1}{2})\tfrac{\phi(p-1)}{\phi\left(\tfrac{p-1}{2}\right)}] \pmod{p}.</math>

Considerando ora il [[polinomio]] monico delle radici primitive modulo <math>p</math> (primo e diverso da <math>3</math>) esso sarà di grado <math>\phi(\phi(p))=\phi (p-1)</math>:

:<math>x^{\phi(p-1)} +A_{n-1} x^{\phi(p-1)-1}+\ldots+A_1 x+A_0\equiv\prod_{(i,p-1)=1} (x-g^i) \pmod{p}.</math>

Riga 115 ⟶ 112:

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}+\ldots+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}+\ldots+(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 <math>p</math> primo e maggiore di <math>3</math> 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>.

Riga 123 ⟶ 120:

Allora in base alle considerazioni precedenti sappiamo:

:<math>x^{\phi(p-1)} -\mu(p-1)x^{\phi(p-1)-1}+\ldots-\mu(p-1)x+1\equiv\prod_{(i,p-1)=1} (x-g^i) \pmod{p}.</math>

Riportiamo alcuni esempi di tali polinomi:

Riga 136 ⟶ 133:

* <math>x^{12}-x^{10}+x^8-x^6+x^4-x^2+1 \equiv 0 \pmod{29}</math>

* <math>x^8+x^7-x^5-x^4-x^3+x+1 \equiv0 \pmod{31}</math>

Si vede che tali polinomi altro non sono che i polinomi ciclotomici <math>\Phi_n(x)</math> dove <math>n=p-1</math> con <math>p</math> numero primo.

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

Riga 150 ⟶ 149:

:<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>. ([[Criterio di Eulero]]) e. poiché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 polinomopolinomio 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.

Riga 181 ⟶ 187:

* [[Tom M. Apostol]] (1976): Introduction to Analytic Number Theory, Springer-Verlag, New York. ISBN 0-387-90163-9 (Capitolo 10).

== Voci correlate ==

*[[Congettura di Artin]]

== Collegamenti esterni ==

*{{Collegamenti esterni}}

{{Portale|matematica}}

[[Categoria:Aritmetica modulare]]