Radice primitiva modulo n

In matematica, in particolare in aritmetica modulare, un generatore modulo ${\displaystyle n}$ o radice primitiva modulo ${\displaystyle n}$ o semplicemente generatore se è chiaro il contesto, è un intero ${\displaystyle g}$ le cui potenze modulo ${\displaystyle n}$ sono congruenti con i numeri coprimi ad ${\displaystyle n}$.

I generatori modulo ${\displaystyle n}$ rivestono un'importanza considerevole in crittografia.

Se ${\displaystyle n\geq 1}$ è un intero, i numeri coprimi ad ${\displaystyle n}$, considerati modulo ${\displaystyle n}$, costituiscono un gruppo rispetto all'operazione di moltiplicazione; esso viene generalmente indicato con ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ oppure ${\displaystyle \mathbb {Z} _{n}^{*}}$. Esso è un gruppo ciclico se e solo se ${\displaystyle n}$ è uguale a ${\displaystyle 2}$, ${\displaystyle 4}$, ${\displaystyle p^{k}}$ o ${\displaystyle 2p^{k}}$ per un numero primo dispari ${\displaystyle p}$ e ${\displaystyle k\geq 1}$. Un generatore di questo gruppo ciclico è chiamato anche elemento primitivo di ${\displaystyle \mathbb {Z} _{n}^{*}}$.

Si consideri per esempio ${\displaystyle n=14}$. Gli elementi di

${\displaystyle (\mathbb {Z} /14\mathbb {Z} )^{*},}$

sono le classi di congruenza di ${\displaystyle 1}$, ${\displaystyle 3}$, ${\displaystyle 5}$, ${\displaystyle 9}$, ${\displaystyle 11}$ e ${\displaystyle 13}$.

Si ha che ${\displaystyle 3}$ è un generatore modulo ${\displaystyle 14}$, perché 3² = 9, 3³ = 13, 3⁴ = 11, 3⁵ = 5 e 3⁶ = 1 (modulo 14). L'unica altra radice primitiva modulo ${\displaystyle 14}$ è ${\displaystyle 5}$.

Trovare i generatori

Di seguito vi è una tabella che contiene i più piccoli generatori per diversi valori di ${\displaystyle n}$ ^[1]:

n	2	3	4	5	6	7	8	9	10	11	12	13	14
generatore mod n	1	2	3	2	5	3	-	2	3	2	-	2	3

Non è nota nessuna formula generale ragionevolmente semplice per determinare i generatori modulo ${\displaystyle n}$ . Vi sono però dei metodi per individuare un generatore che sono più veloci della semplice verifica per tentativi di tutti i candidati. Se l'ordine moltiplicativo di un numero ${\displaystyle m}$  modulo ${\displaystyle n}$  è uguale all'ordine di ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ , cioè a ${\displaystyle \phi (n)}$ , dove ${\displaystyle \phi }$  è la funzione phi di Eulero, allora ${\displaystyle m}$  è un generatore. Si può utilizzare il seguente test per i generatori: calcolare ${\displaystyle \phi (n)}$ . Quindi determinare i diversi fattori primi di ${\displaystyle \phi (n)}$ , siano ${\displaystyle p_{1},\ldots ,p_{k}}$ . Ora, per ogni elemento ${\displaystyle m}$  di ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ , calcolare

${\displaystyle m^{\phi (n)/p_{i}}\mod n\qquad {\text{ per }}i=1,\ldots ,k}$ 

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

Il numero di generatori modulo ${\displaystyle n}$ , se ne esistono, è uguale a ${\displaystyle \phi (\phi (n))}$  dal momento che, in generale, un gruppo ciclico di ${\displaystyle r}$  elementi possiede ${\displaystyle \phi (r)}$  generatori.

A volte si può essere interessati ai generatori piccoli. Al riguardo sono stati dimostrati i seguenti risultati:

• per ogni ${\displaystyle \varepsilon >0}$  esistono delle costanti positive ${\displaystyle C}$  e ${\displaystyle p_{0}}$  tali che, per ogni primo ${\displaystyle p\geq p_{0}}$ , esiste un generatore modulo ${\displaystyle p}$  minore di ${\displaystyle Cp^{1/4+\varepsilon }}$ ;

• se l'ipotesi di Riemann generalizzata è vera, allora, per ogni numero primo ${\displaystyle p}$ , esiste un generatore modulo ${\displaystyle p}$  minore di ${\displaystyle 70\ln ^{2}p}$ .

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 ${\displaystyle p}$ , poi dimostrando che, se ${\displaystyle a}$  è una radice primitiva di ${\displaystyle p}$ , allora o ${\displaystyle a}$  o ${\displaystyle p+a}$  è una radice primitiva di ${\displaystyle p^{2}}$ , e che questa è poi radice primitiva anche di ogni potenza successiva di ${\displaystyle p}$ . Infatti, sia ${\displaystyle a}$  una radice primitiva modulo ${\displaystyle p}$ . Allora, per definizione di radice primitiva

${\displaystyle a^{p-1}\equiv 1\mod p,}$ 

e ${\displaystyle p-1}$  è il più piccolo esponente per cui ciò avviene. Poiché ${\displaystyle \phi (p^{2})=p(p-1)}$ , l'ordine moltiplicativo di ${\displaystyle a}$  modulo ${\displaystyle p^{2}}$  divide ${\displaystyle p(p-1)}$ , ed è multiplo di ${\displaystyle p-1}$ , e quindi può essere solamente ${\displaystyle p-1}$  o lo stesso ${\displaystyle p(p-1)}$ . In quest'ultimo caso ${\displaystyle a}$  è una radice primitiva modulo ${\displaystyle p^{2}}$ ; altrimenti, sviluppiamo con la formula del binomio di Newton

${\displaystyle (p+a)^{p-1}=p^{p-1}+\cdots +{\binom {p-1}{p-2}}pa^{p-2}+a^{p-1}\equiv (p-1)pa^{p-2}+a^{p-1}\mod p^{2}\equiv 1-pa^{p-2}\mod p^{2},}$ 

che non può essere ${\displaystyle 1}$ , perché altrimenti ${\displaystyle p}$  dividerebbe ${\displaystyle a^{p-2}}$ , il che è assurdo, e quindi l'ordine di ${\displaystyle p+a}$  non è ${\displaystyle p-1}$ , e deve essere ${\displaystyle p(p-1)}$ , cioè abbiamo trovato una radice primitiva modulo ${\displaystyle p^{2}}$ .

Per dimostrare la proposizione per ${\displaystyle p^{k}}$ , con ${\displaystyle k>2}$ , si procede per induzione: supponiamo che ${\displaystyle a}$  sia una radice primitiva per tutti i ${\displaystyle p^{j}}$  con ${\displaystyle j<k}$ . In particolare

${\displaystyle a^{\phi (p^{k-2})}\equiv 1\mod p^{k-2},}$ 

ovvero

${\displaystyle a^{\phi (p^{k-2})}=1+lp^{k-2},}$ 

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

${\displaystyle 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}.}$ 

Questa quantità è uguale a ${\displaystyle 1}$  se e solo se ${\displaystyle l}$  è divisibile per ${\displaystyle p}$ ; tuttavia, se lo fosse, si avrebbe

${\displaystyle a^{\phi (p^{k-2})}=1+lp^{k-2}\equiv 1\mod p^{k-1}}$ 

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

L'estensione ai numeri nella forma ${\displaystyle 2p^{k}}$  segue immediatamente, perché il gruppo moltiplicativo di questo anello contiene lo stesso numero di elementi di quello dell'anello di ${\displaystyle p^{k}}$  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 ${\displaystyle g}$  il generatore di ${\displaystyle \mathbb {Z} _{p}^{*}}$  allora, per quanto precedentemente esposto, tutte le radici primitive modulo ${\displaystyle p}$  si potranno esprimere come ${\displaystyle g^{i}}$  dove ${\displaystyle (i,\phi (p))=(i,p-1)=1}$  .

Gauss nelle Disquisitiones Arithmeticae dimostrò agli articoli 80 ed 81 il valore (modulo ${\displaystyle p}$  primo) della somma delle radici primitive di ${\displaystyle \mathbb {Z} _{p}}$  e del loro prodotto.

Esse valgono:

• ${\displaystyle \prod _{(i,p-1)=1}g^{i}\equiv 1{\pmod {p}}}$  dove ${\displaystyle p}$  primo diverso da ${\displaystyle 3}$ .(Art.80, DA)
• ${\displaystyle \sum _{(i,p-1)=1}g^{i}\equiv \mu (p-1){\pmod {p}}}$  per qualsiasi ${\displaystyle p}$  primo, ${\displaystyle \mu }$  è 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)

La seconda identità si può estendere considerando tutti gli elementi di ordine ${\displaystyle d}$ , con ${\displaystyle d}$  divisore di ${\displaystyle p-1}$ . Sia ${\displaystyle h}$  un elemento di ${\displaystyle \mathbb {Z} _{p}^{*}}$  di ordine ${\displaystyle d}$ , allora tutti gli elementi di ordine d saranno del tipo ${\displaystyle h^{j}}$  con ${\displaystyle (j,d)=1}$  e quindi saranno in numero ${\displaystyle \phi (d)}$ . La loro somma vale

${\displaystyle \sum _{(j,d)=1}h^{j}\equiv \mu (d){\pmod {p}}.}$ 

Tramite tale formula possiamo calcolare la somma delle potenze ${\displaystyle k}$ -esime delle radici primitive. Supponiamo che ${\displaystyle k}$  sia tale che ${\displaystyle (k,p-1)=1}$  allora tale elevamento a potenza ${\displaystyle k}$  manda l'insieme delle radici primitive in sé stesso e pertanto

${\displaystyle \sum _{(i,p-1)=1}(g^{i})^{k}\equiv \mu (p-1){\pmod {p}}.}$ 

Ora consideriamo un ${\displaystyle k}$  che divida interamente ${\displaystyle p-1}$ , se ${\displaystyle g}$  è radice primitiva (e quindi ha ordine ${\displaystyle p-1}$ ), l'elemento ${\displaystyle g^{k}}$  avrà ordine uguale a ${\displaystyle {\tfrac {p-1}{k}}}$  quindi l'insieme delle radici primitive (ossia l'insieme degli elementi di ordine ${\displaystyle p-1}$ ) viene mandato nell'insieme degli elementi di ordine ${\displaystyle {\tfrac {p-1}{k}}}$  che ha cardinalità ${\displaystyle \phi ({\tfrac {p-1}{k}})}$ . Tale funzione è iniettiva se e solo se ${\displaystyle k=1}$  mentre negli altri casi si assiste ad una "restrizione" delle radici primitive, nel senso che ${\displaystyle {\tfrac {\phi (p-1)}{\phi \left({\tfrac {p-1}{k}}\right)}}}$  radici primitive vengono mandate nello stesso elemento di ordine ${\displaystyle {\tfrac {p-1}{k}}}$ . Tale funzione è suriettiva, detto ciò per calcolare

${\displaystyle \sum _{(i,p-1)=1}(g^{i})^{k},}$ 

basta calcolare la sommatoria degli elementi di ordine ${\displaystyle {\tfrac {p-1}{k}}}$  e moltiplicare tale valore per l'"indice di restrizione" ${\displaystyle {\tfrac {\phi (p-1)}{\phi \left({\tfrac {p-1}{k}}\right)}}}$ . Quindi

${\displaystyle \sum _{(i,p-1)=1}(g^{i})^{k}={\tfrac {\phi (p-1)}{\phi \left({\tfrac {p-1}{k}}\right)}}\mu ({\tfrac {p-1}{k}}).}$ 

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

${\displaystyle \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)}}).}$ 

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:

${\displaystyle \sum _{(ij,p-1)=1;i\neq j}g^{i}g^{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}}.}$ 

Considerando ora il polinomio monico delle radici primitive modulo ${\displaystyle p}$  (primo e diverso da ${\displaystyle 3}$ ) esso sarà di grado ${\displaystyle \phi (\phi (p))=\phi (p-1)}$ :

${\displaystyle 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}}.}$ 

Si dimostra che valgono le relazioni ${\displaystyle A_{i}=A_{\phi (p-1)-i}}$ . Infatti se ${\displaystyle y}$  è una radice primitiva allora anche ${\displaystyle y^{-1}}$  lo è, e tali radici sono distinte per ${\displaystyle p}$  diverso da ${\displaystyle 3}$ . Valutando i polinomi in queste radici otteniamo:

(1) ${\displaystyle y^{\phi (p-1)}+A_{n-1}y^{\phi (p-1)-1}+\ldots +A_{1}y+A_{0}\equiv 0{\pmod {p}}}$ 

(2) ${\displaystyle ({\tfrac {1}{y}})^{\phi (p-1)}+A_{n-1}({\tfrac {1}{y}})^{\phi (p-1)-1}+\ldots +A_{1}({\tfrac {1}{y}})+A_{0}\equiv 0{\pmod {p}}}$ 

moltiplicando la (2) per ${\displaystyle ({\tfrac {1}{y}})^{\phi (p-1)}}$  otteniamo:

(2) ${\displaystyle A_{0}y^{\phi (p-1)}+A_{1}y^{\phi (p-1)-1}+\ldots +A_{n-1}y+1\equiv 0{\pmod {p}}}$  Sottraendo la (1) alla (2') otteniamo:

(3) ${\displaystyle (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}}}$ 

In particolare il termine ${\displaystyle A_{0}}$  vale ${\displaystyle (-1)^{\phi (p-1)}\prod _{(i,p-1)=1}g^{i}}$  dove p diverso da tre, pertanto per qualsiasi ${\displaystyle p}$  primo e maggiore di ${\displaystyle 3}$  si ha che ${\displaystyle \phi (p-1)}$  è pari e quindi ${\displaystyle A_{0}\equiv 1{\pmod {p}}}$ . Sostituendo tale valore nella (3) otteniamo che l'equazione ha, quindi, grado ${\displaystyle \phi (p-1)-1}$  e della quale due radici sono ${\displaystyle y}$  e ${\displaystyle y^{-1}}$ ; 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 ${\displaystyle \phi (p-1)}$  radici primitive ed ha grado ${\displaystyle \phi (p-1)-1}$ . Ma allora è identicamente nulla e quindi ${\displaystyle A_{i}=A_{\phi (p-1)-i}}$ .

Allora in base alle considerazioni precedenti sappiamo:

${\displaystyle 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}}.}$ 

Riportiamo alcuni esempi di tali polinomi:

• ${\displaystyle x+1\equiv 0{\pmod {3}}}$  (per questo non si può impiegare l'Art.80 di Gauss, ma si è solo verificato "a mano")
• ${\displaystyle x^{2}+1\equiv 0{\pmod {5}}}$ 
• ${\displaystyle x^{2}-x+1\equiv 0{\pmod {7}}}$ 
• ${\displaystyle x^{4}-x^{3}+x^{2}-x+1\equiv 0{\pmod {11}}}$ 
• ${\displaystyle x^{4}-x^{2}+1\equiv 0{\pmod {13}}}$ 
• ${\displaystyle x^{8}+1\equiv 0{\pmod {17}}}$ 
• ${\displaystyle x^{6}-x^{3}+1\equiv 0{\pmod {19}}}$ 
• ${\displaystyle x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1\equiv 0{\pmod {23}}}$ 
• ${\displaystyle x^{12}-x^{10}+x^{8}-x^{6}+x^{4}-x^{2}+1\equiv 0{\pmod {29}}}$ 
• ${\displaystyle x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1\equiv 0{\pmod {31}}}$ 

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

In particolare se ${\displaystyle p}$  è un numero primo di Fermat allora il polinomio delle sue radici primitive sarà:

${\displaystyle x^{\tfrac {p-1}{2}}+1\equiv 0{\pmod {p}}.}$ 

Infatti se ${\displaystyle p}$  è un primo di Fermat esso è del tipo ${\displaystyle p=2^{2^{n}}+1}$  ed il numero delle radici primitive sarà

${\displaystyle \phi (\phi (p))=\phi (p-1)=\phi (2^{2^{n}})=2^{2^{n}-1},}$ 

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 ${\displaystyle \mathbb {Z} _{p}^{*}}$  è

${\displaystyle x^{p-1}-1\equiv (x^{\tfrac {p-1}{2}}-1)(x^{\tfrac {p-1}{2}}+1)\equiv 0{\pmod {p}},}$ 

dove il primo polinomio si annulla solo e solamente per i residui quadratici modulo ${\displaystyle 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 ${\displaystyle {\tfrac {p-1}{2}}=2^{2^{n}-1}}$ , cioè ha lo stesso grado del polinomo cercato: pertanto lo è.

Note

1. ^ (EN) Sequenza A046145, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.

Bibliografia

• 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

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica