Radice primitiva modulo n

In aritmetica modulare, una radice primitiva modulo $n$ o generatore modulo $n$ (o semplicemente generatore) è un numero intero le cui potenze modulo $n$ sono congruenti con i numeri coprimi ad $n$ .

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

Si consideri per esempio $n=14$ . Gli elementi di

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

sono le classi di congruenza di $1$ , $3$ , $5$ , $9$ , $11$ e $13$ che sono coprimi con $n=14.$

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

I generatori modulo $n$ rivestono un'importanza considerevole in crittografia.

Trovare i generatori

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 all'ordine di $(\mathbb {Z} /n\mathbb {Z} )^{*}$ , cioè a $\phi (n)$ , dove $\phi$ è la funzione phi di Eulero, allora $m$ è un generatore. Si può utilizzare il seguente test per i generatori: calcolare $\phi (n)$ . Quindi determinare i diversi fattori primi di $\phi (n)$ , siano $p_{1},\ldots ,p_{k}$ . Ora, per ogni elemento $m$ di $(\mathbb {Z} /n\mathbb {Z} )^{*}$ , calcolare

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 $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 $\phi (\phi (n))$ dal momento che, in generale, un gruppo ciclico di $r$ elementi possiede $\phi (r)$ generatori.

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

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

se l'ipotesi di Riemann generalizzata è vera, allora, per ogni numero primo $p$ , esiste un generatore modulo $p$ minore di $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 $p$ , poi dimostrando che, se $a$ è una radice primitiva di $p$ , allora o $a$ o $p+a$ è una radice primitiva di $p^{2}$ , 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

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

e $p-1$ è il più piccolo esponente per cui ciò avviene. Poiché $\phi (p^{2})=p(p-1)$ , l'ordine moltiplicativo di $a$ modulo $p^{2}$ 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^{2}$ ; altrimenti, sviluppiamo con la formula del binomio di Newton

(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^{2}$ .

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

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

ossia

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 $\phi (p^{k-1})$ , perché ha quest'ordine modulo $p^{k-1}$ . Quindi, poiché $\phi (p^{k})=p\phi (p^{k-1})$ , l'ordine può essere solo $\phi (p^{k-1})$ o $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

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

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 $\phi (p^{k-1})$ . Questo è assurdo, e quindi l'ordine di $a$ modulo $p^{k}$ è esattamente $\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 $g$ il generatore di $\mathbb {Z} _{p}^{*}$ allora, per quanto precedentemente esposto, tutte le radici primitive modulo $p$ si potranno esprimere come $g^{i}$ dove $(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 $\mathbb {Z} _{p}$ e del loro prodotto.

Esse valgono:

$\prod _{(i,p-1)=1}g^{i}\equiv 1{\pmod {p}}$ dove $p$ primo diverso da $3$ .(Art.80, DA)
$\sum _{(i,p-1)=1}g^{i}\equiv \mu (p-1){\pmod {p}}$ per qualsiasi $p$ primo, $\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 $d$ , con $d$ divisore di $p-1$ . Sia $h$ un elemento di $\mathbb {Z} _{p}^{*}$ di ordine $d$ , allora tutti gli elementi di ordine d saranno del tipo $h^{j}$ con $(j,d)=1$ e quindi saranno in numero $\phi (d)$ . La loro somma vale

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

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

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

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

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

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

\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 $k$ dove $(k,p-1)=b$ , quindi $k=ab$ e $(a,p-1)=1$ pertanto al posto di applicare direttamente la potenza $k$ alle radici primitive, prima applichiamo la potenza $a$ e poi, agli elementi ottenuti, la potenza $b$ . La potenza $a$ manda le radici primitive in sé stesse, la potenza $b$ le fa "restringere" in un sottordine e pertanto, indicando $(k,p-1)$ in luogo di $b$ otteniamo:

\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:

\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 $p$ (primo e diverso da $3$ ) esso sarà di grado $\phi (\phi (p))=\phi (p-1)$ :

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 $A_{i}=A_{\phi (p-1)-i}$ . Infatti se $y$ è una radice primitiva allora anche $y^{-1}$ lo è, e tali radici sono distinte per $p$ diverso da $3$ . Valutando i polinomi in queste radici otteniamo:

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

(2) $({\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 $({\tfrac {1}{y}})^{\phi (p-1)}$ otteniamo:

(2) $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) $(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 $A_{0}$ vale $(-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 $\phi (p-1)$ è pari e quindi $A_{0}\equiv 1{\pmod {p}}$ . Sostituendo tale valore nella (3) otteniamo che l'equazione ha, quindi, grado $\phi (p-1)-1$ e della quale due radici sono $y$ e $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 $\phi (p-1)$ radici primitive ed ha grado $\phi (p-1)-1$ . Ma allora è identicamente nulla e quindi $A_{i}=A_{\phi (p-1)-i}$ .

Allora in base alle considerazioni precedenti sappiamo:

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:

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

Si vede che tali polinomi altro non sono che i polinomi ciclotomici $\Phi _{n}(x)$ dove $n=p-1$ con $p$ numero primo.

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 anche 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 numero primo di Fermat allora il polinomio delle sue radici primitive sarà:

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

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

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

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. Poiché le radici primitive non sono residui quadratici, il polinomio delle radici primitive deve fattorizzare il secondo polinomio. Quest'ultimo è monico e di grado ${\tfrac {p-1}{2}}=2^{2^{n}-1}$ , cioè ha lo stesso grado del polinomio cercato: pertanto lo è.

Se $p$ è un numero primo sicuro maggiore di $5$ , ossia se $p=2q+1$ dove $q$ è un primo di Sophie Germain maggiore di $2$ , il polinomio delle radici primitive ha coefficienti di valori alternativamente $+1$ e $-1$ . Infatti in tal caso si ha che la cardinalità di $\mathbb {Z} _{p}^{*}$ è $2q$ e pertanto gli elementi di $\mathbb {Z} _{p}^{*}$ possono avere ordine solo di $2q,q,2,1$ . Per l'ordine $1$ abbiamo solo l'elemento $+1$ , mentre per l'ordine $2$ abbiamo solo l'elemento $-1$ . Gli elementi di ordine $2q$ sono equinumerosi agli elementi di ordine $q$ , infatti $\phi (2q)=\phi (q)=q-1$ . Sia $h$ un elemento di ordine $q$ allora, poiché $q$ è coprimo con $2$ , l'elemento $-h$ ha ordine pari al minimo comune multiplo tra l'ordine di $-1$ (che è $2$ ) e quello di $h$ (che è $q$ ). In sintesi per ogni elemento $h$ di ordine $q$ abbiamo che l'elemento $-h$ ha ordine $2q$ .

Sia il polinomio delle radici di ordine $q$ il seguente:

p_{q}(x)=x^{q-1}+M_{q-2}x^{q-2}\ldots +M_{2}x^{2}+M_{1}x+M_{0},

ma allora il polinomio delle radici di ordine $2q$ (radici primitive) sarà:

p_{2q}(x)=x^{q-1}-M_{q-2}x^{q-2}\ldots +M_{2}x^{2}-M_{1}x+M_{0},

in quanto ogni coefficiente di $p_{2q}(x)$ è somma di prodotti di $s$ radici opposte a quelle di $p_{q}(x)$ , quindi il segno dipende dalla parità di $s$ .

Per quanto appena affermato, proponiamoci di determinare il polinomio delle radici di ordine $q$ al fine di determinare quello di ordine $2q$ . Sia $h$ un elemento di ordine $q$ allora tutti gli altri elementi di pari ordine si esprimeranno come $h^{i}$ con $(i,q)=1$ e $q$ , ricordiamo, è numero primo maggiore di $2$ . Esse saranno pertanto $h^{1},h^{2},h^{3},\ldots ,h^{q-1}$ e se ad esse aggiungiamo l'elemento $1$ allora sappiamo che esse sono le radici dell'equazione