Radice primitiva modulo n

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

Un generatore o radice primitiva modulo n è un concetto dell'aritmetica modulare, in teoria dei numeri. Se n≥1 è un intero, i numeri coprimi ad n, considerati modulo n, costituiscono un gruppo rispetto all'operazione di moltiplicazione; esso viene generalmente indicato con (Z/nZ)^× 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 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.

Si consideri per esempio n = 14. Gli elementi di

(Z/14Z)^×

sono le classi di congruenza di

1, 3, 5, 9, 11 e 13.

3 è un generatore modulo 14, perché 3² = 9, 3³ = 13, 3⁴ = 11, 3⁵ = 5 e 3⁶ = 1 (modulo 14). L'unica altra radice primitiva modulo 14 è 5.

Di seguito vi è una tabella che contiene i più piccoli generatori per diversi valori di 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 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 m modulo n è uguale alla φ(n) (l'ordine di Z/nZ)^×), allora m è un generatore. Si può utilizzare questo test per i generatori:

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

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

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.

Il numero di generatori modulo n, se ne esistono, è uguale a

φ(φ(n))

dal momento che, in generale, un gruppo ciclico di r elementi possiede φ(r) generatori.

A volte si può essere interessati nei generatori piccoli. Al riguardo sono stati dimostrati i seguenti risultati. Per ogni ε>0 esistono delle costanti positive C e p₀ tali che, per ogni primo p ≥ p₀, esiste un generatore modulo p minore di

C p^1/4+ε.

Se l'ipotesi di Riemann generalizzata è vera, allora, per ogni numero primo p, esiste un generatore modulo p minore di

70 (ln(p))².

I generatori modulo m rivestono un'importanza considerevole in crittografia.

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

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

e p-1 è il più piccolo esponente per cui ciò avviene. Poiché ${\displaystyle \phi (p^{2})=p(p-1)}$ , l'ordine moltiplicativo di a modulo p² divide p(p-1), ed è multiplo di p-1, e quindi può essere solamente p-1 o lo stesso p(p-1). In quest'ultimo caso a è una radice primitiva modulo p²; 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 1, perché altrimenti p dividerebbe a^p-2, il che è assurdo, e quindi l'ordine di p+a non è p-1, e deve essere p(p-1), cioè abbiamo trovato una radice primitiva modulo p².

Per dimostrare la proposizione per p^k, con k>2, si procede per induzione: supponiamo che a sia una radice primitiva per tutti i p^j con 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 l. Questa relazione vale anche modulo p^k; inoltre l'ordine di a modulo p^k deve essere un multiplo di ${\displaystyle \phi (p^{k-1})}$ , perché ha quest'ordine modulo 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, a è una radice primitiva se il suo ordine è il secondo di questi valori. Se 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 1 se e solo se l è divisibile per 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 a modulo p^k-1 sia ${\displaystyle \phi (p^{k-1})}$ . Questo è assurdo, e quindi l'ordine di a modulo p^k è esattamente ${\displaystyle \phi (p^{k})}$ , e a è una radice primitiva modulo p^k. Per induzione questo è valido per ogni k.

L'estensione ai numeri nella forma 2p^k segue immediatamente, perché il gruppo moltiplicativo di questo anello contiene lo stesso numero di elementi di quello dell'anello di 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 Z_{p}^{*}}$  allora, per quanto precedentemente esposto, tutte le radici primitive modulo 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 p primo) della somma delle radici primitive di ${\displaystyle Z_{p}}$  e del loro prodotto.

Esse valgono:

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

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 ${\displaystyle \mu (d)}$  e di ${\displaystyle \phi (d)}$  ove d sono i divisori di p-1.

Considerando ora il polinomio monico delle radici primitive modulo p,(primo e diverso da 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}+...+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}}$  la è e tali radici sono distinte per p diverso da tre. Valutando i polinomi in queste radici otteniamo:

(1) ${\displaystyle y^{\phi (p-1)}+A_{n-1}y^{\phi (p-1)-1}+...+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}+...+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}+...+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}+...+(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 p primo e maggiore di 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}}$  .

In base alle considerazioni precedenti sappiamo:

${\displaystyle x^{\phi (p-1)}-\mu (p-1)x^{\phi (p-1)-1}+...-\mu (p-1)x+1\equiv \prod _{(i,p-1)=1}(x-g^{i}){\pmod {p}}}$ 

Possiamo, dopo il relativo calcolo, affermare che il coefficiente ${\displaystyle A_{2}}$  varrà: ${\displaystyle A_{2}\equiv {\tfrac {1}{2}}[(\mu (p-1))^{2}-\mu ({\tfrac {p-1}{2}}){\tfrac {\phi (p-1)}{\phi ({\tfrac {p-1}{2}})}}]{\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}}}$ 

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à: ${\displaystyle x^{\tfrac {p-1}{2}}+1\equiv 0{\pmod {p}}}$  .

Infatti se 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 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 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