In aritmetica modulare, una radice primitiva modulo
o generatore modulo
(o semplicemente generatore) è un numero intero le cui potenze modulo
sono congruenti con i numeri coprimi ad
.
Se
è un intero, i numeri coprimi ad
, considerati modulo
, costituiscono un gruppo rispetto all'operazione di moltiplicazione; esso viene generalmente indicato con
oppure
. Esso è un gruppo ciclico se e solo se
è uguale a
,
,
o
per un numero primo dispari
e
. Un generatore di questo gruppo ciclico è chiamato anche elemento primitivo di
.
Si consideri per esempio
. Gli elementi di
![{\displaystyle (\mathbb {Z} /14\mathbb {Z} )^{*},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5846d8aba322bdc06c4e3ceee35b88621cd6e967)
sono le classi di congruenza di
,
,
,
,
e
che sono coprimi con
Si ha che
è un generatore modulo
, perché 32 mod 14 = 9, 33 mod 14 = 13, 34 mod 14 = 11, 35 mod 14 = 5 e 36 mod 14 = 1. L'unica altra radice primitiva modulo
è
.
I generatori modulo
rivestono un'importanza considerevole in crittografia.
Di seguito vi è una tabella che contiene i più piccoli generatori per diversi valori di
[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
. 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
modulo
è uguale all'ordine di
, cioè a
, dove
è la funzione phi di Eulero, allora
è un generatore. Si può utilizzare il seguente test per i generatori: calcolare
. Quindi determinare i diversi fattori primi di
, siano
. Ora, per ogni elemento
di
, calcolare
![{\displaystyle m^{\phi (n)/p_{i}}\mod n\qquad {\text{ per }}i=1,\ldots ,k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a78e0af00447776f28fd93cd0a63aca54b17f700)
usando il rapido algoritmo di esponenziazione mediante elevamento al quadrato. Non appena si trova un numero
per il quale questi
risultati sono tutti diversi da
, allora
è un generatore.
Il numero di generatori modulo
, se ne esistono, è uguale a
dal momento che, in generale, un gruppo ciclico di
elementi possiede
generatori.
A volte si può essere interessati ai generatori piccoli. Al riguardo sono stati dimostrati i seguenti risultati:
- per ogni
esistono delle costanti positive
e
tali che, per ogni primo
, esiste un generatore modulo
minore di
;
- se l'ipotesi di Riemann generalizzata è vera, allora, per ogni numero primo
, esiste un generatore modulo
minore di
.
La dimostrazione dell'esistenza del generatore procede dapprima provando che essa esiste per ogni numero primo
, poi dimostrando che, se
è una radice primitiva di
, allora o
o
è una radice primitiva di
, e che questa è poi radice primitiva anche di ogni potenza successiva di
. Infatti, sia
una radice primitiva modulo
. Allora, per definizione di radice primitiva
![{\displaystyle a^{p-1}\equiv 1\mod p,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24a01e2aeba0784705482b0737647a017630c47d)
e
è il più piccolo esponente per cui ciò avviene. Poiché
, l'ordine moltiplicativo di
modulo
divide
, ed è multiplo di
, e quindi può essere solamente
o lo stesso
. In quest'ultimo caso
è una radice primitiva modulo
; 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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a8fd9ad634011d0eeb72246680c4e6731e740ef)
che non può essere
, perché altrimenti
dividerebbe
, il che è assurdo, e quindi l'ordine di
non è
, e deve essere
, cioè abbiamo trovato una radice primitiva modulo
.
Per dimostrare la proposizione per
, con
, si procede per induzione: supponiamo che
sia una radice primitiva per tutti i
con
. In particolare
![{\displaystyle a^{\phi (p^{k-2})}\equiv 1\mod p^{k-2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d211c336feae81a0bfb9fef4df2c3c4dde131a66)
ossia
![{\displaystyle a^{\phi (p^{k-2})}=1+lp^{k-2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a98429658bea0c66ccd672357949192919e61db)
per un qualche
. Questa relazione vale anche modulo
; inoltre l'ordine di
modulo
deve essere un multiplo di
, perché ha quest'ordine modulo
. Quindi, poiché
, l'ordine può essere solo
o
; in particolare,
è una radice primitiva se il suo ordine è il secondo di questi valori. Se
è 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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6479585bb54b6bb5dd4635c7fd6ac78e44dd437)
Questa quantità è uguale a
se e solo se
è divisibile per
; tuttavia, se lo fosse, si avrebbe
![{\displaystyle a^{\phi (p^{k-2})}=1+lp^{k-2}\equiv 1\mod p^{k-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13ff849834b36cdb103116ce2b78498fea1cb976)
contro l'ipotesi che l'ordine di
modulo
sia
. Questo è assurdo, e quindi l'ordine di
modulo
è esattamente
, e
è una radice primitiva modulo
. Per induzione questo è valido per ogni
.
L'estensione ai numeri nella forma
segue immediatamente, perché il gruppo moltiplicativo di questo anello contiene lo stesso numero di elementi di quello dell'anello di
elementi, ed esiste una corrispondenza biunivoca che conserva le operazioni (ossia un isomorfismo) tra questi due gruppi.
Indicando con
il generatore di
allora, per quanto precedentemente esposto, tutte le radici primitive modulo
si potranno esprimere come
dove
Gauss nelle Disquisitiones Arithmeticae dimostrò agli articoli 80 ed 81 il valore (modulo
primo) della somma delle radici primitive di
e del loro prodotto.
Esse valgono:
dove
primo diverso da
.(Art.80, DA)
per qualsiasi
primo,
è 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
, con
divisore di
. Sia
un elemento di
di ordine
, allora tutti gli elementi di ordine d saranno del tipo
con
e quindi saranno in numero
. La loro somma vale
![{\displaystyle \sum _{(j,d)=1}h^{j}\equiv \mu (d){\pmod {p}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab133951146b53b606f5e91bc36ba393dc0083ad)
Tramite tale formula possiamo calcolare la somma delle potenze
-esime delle radici primitive. Supponiamo che
sia tale che
allora tale elevamento a potenza
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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d93e726fafeb2d90199d9a71c83bcd2ed8220902)
Ora consideriamo un
che divida interamente
, se
è radice primitiva (e quindi ha ordine
), l'elemento
avrà ordine uguale a
quindi l'insieme delle radici primitive (ossia l'insieme degli elementi di ordine
) viene mandato nell'insieme degli elementi di ordine
che ha cardinalità
. Tale funzione è iniettiva se e solo se
mentre negli altri casi si assiste ad una "restrizione" delle radici primitive, nel senso che
radici primitive vengono mandate nello stesso elemento di ordine
. Tale funzione è suriettiva, detto ciò per calcolare
![{\displaystyle \sum _{(i,p-1)=1}(g^{i})^{k},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/56d4ea2d73dc49dbf827f57251f2bdb185da983d)
basta calcolare la sommatoria degli elementi di ordine
e moltiplicare tale valore per l'"indice di restrizione"
. 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}}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2b87c5197f4d59691027acff1924875820e3e10)
Sia ora
dove
, quindi
e
pertanto al posto di applicare direttamente la potenza
alle radici primitive, prima applichiamo la potenza
e poi, agli elementi ottenuti, la potenza
. La potenza
manda le radici primitive in sé stesse, la potenza
le fa "restringere" in un sottordine e pertanto, indicando
in luogo di
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)}}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd33732b43827a71bd8ba2ddaecc8ddb970df9a0)
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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe8fd2e3fe12dcece8a0f520c7ab666d01ebd34e)
Considerando ora il polinomio monico delle radici primitive modulo
(primo e diverso da
) esso sarà di grado
:
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68200645f1fb5d2342fe5a53151b7352bd07f1d1)
Si dimostra che valgono le relazioni
. Infatti se
è una radice primitiva allora anche
lo è, e tali radici sono distinte per
diverso da
. Valutando i polinomi in queste radici otteniamo:
(1)
(2)
moltiplicando la (2) per
otteniamo:
(2)
Sottraendo la (1) alla (2') otteniamo:
(3)
In particolare il termine
vale
dove p diverso da tre, pertanto per qualsiasi
primo e maggiore di
si ha che
è pari e quindi
. Sostituendo tale valore nella (3) otteniamo che l'equazione ha, quindi, grado
e della quale due radici sono
e
; 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
radici primitive ed ha grado
. Ma allora è identicamente nulla e quindi
.
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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5a5eda9e08265baca54b7c2fb6f2e8a4e7cb0ed)
Riportiamo alcuni esempi di tali polinomi:
(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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddef5921fb4158021188031631f3f13670562c74)
![{\displaystyle x^{2}-x+1\equiv 0{\pmod {7}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/864df9f7702d8825578a6e63cca50d356f78286d)
![{\displaystyle x^{4}-x^{3}+x^{2}-x+1\equiv 0{\pmod {11}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9f3befc91dfae39c99e7e9f5a85bb27781a07a0)
![{\displaystyle x^{4}-x^{2}+1\equiv 0{\pmod {13}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd77facb2f330742319e3e2cd594d09205f10f26)
![{\displaystyle x^{8}+1\equiv 0{\pmod {17}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/446e58384be171dcea77fbc9045783f3c5175118)
![{\displaystyle x^{6}-x^{3}+1\equiv 0{\pmod {19}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45ca4aebf309082db103a887bbdf7968ba18d0c6)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c9c1a07980c70015804b0cd56493227f10021c0)
![{\displaystyle x^{12}-x^{10}+x^{8}-x^{6}+x^{4}-x^{2}+1\equiv 0{\pmod {29}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20e93a1c076df904fbcb3f6b85958c2abc9d93e9)
![{\displaystyle x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1\equiv 0{\pmod {31}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb752c94b98c25ee1ce7be32c3dee4330732206f)
Si vede che tali polinomi altro non sono che i polinomi ciclotomici
dove
con
numero primo.
Laddove nel polinomio si assiste ad un "passo" costante tra gli esponenti di
(per esempio per
il passo degli esponenti è
, come succede anche per
) e nominando
il valore di tale "passo", allora in tali moduli l'insieme delle radici primitive è quozientabile tramite il gruppo delle radici
-esime dell'unità, e vale il viceversa.
In particolare se
è un numero primo di Fermat allora il polinomio delle sue radici primitive sarà:
![{\displaystyle x^{\tfrac {p-1}{2}}+1\equiv 0{\pmod {p}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f248acb2c754af3aa823e59bcd716da22953853)
Infatti se
è un primo di Fermat esso è del tipo
ed il numero delle radici primitive sarà
![{\displaystyle \phi (\phi (p))=\phi (p-1)=\phi (2^{2^{n}})=2^{2^{n}-1},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/673895e15a9f7a10dc1e6723c883b9ec9deee5f1)
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 x^{p-1}-1\equiv (x^{\tfrac {p-1}{2}}-1)(x^{\tfrac {p-1}{2}}+1)\equiv 0{\pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81dcc7f82f3cb0f1ddbdfefa2edf981dbec00965)
dove il primo polinomio si annulla solo e solamente per i residui quadratici modulo
. 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
, cioè ha lo stesso grado del polinomio cercato: pertanto lo è.
Se
è un numero primo sicuro maggiore di
, ossia se
dove
è un primo di Sophie Germain maggiore di
, il polinomio delle radici primitive ha coefficienti di valori alternativamente
e
. Infatti in tal caso si ha che la cardinalità di
è
e pertanto gli elementi di
possono avere ordine solo di
. Per l'ordine
abbiamo solo l'elemento
, mentre per l'ordine
abbiamo solo l'elemento
. Gli elementi di ordine
sono equinumerosi agli elementi di ordine
, infatti
. Sia
un elemento di ordine
allora, poiché
è coprimo con
, l'elemento
ha ordine pari al minimo comune multiplo tra l'ordine di
(che è
) e quello di
(che è
). In sintesi per ogni elemento
di ordine
abbiamo che l'elemento
ha ordine
.
Sia il polinomio delle radici di ordine
il seguente:
![{\displaystyle p_{q}(x)=x^{q-1}+M_{q-2}x^{q-2}\ldots +M_{2}x^{2}+M_{1}x+M_{0},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d68757ee22d94241f96d11436f72b0cf48bf0d0b)
ma allora il polinomio delle radici di ordine
(radici primitive) sarà:
![{\displaystyle p_{2q}(x)=x^{q-1}-M_{q-2}x^{q-2}\ldots +M_{2}x^{2}-M_{1}x+M_{0},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b40133c5be91148de1ebab8483dfba58c2072a9e)
in quanto ogni coefficiente di
è somma di prodotti di
radici opposte a quelle di
, quindi il segno dipende dalla parità di
.
Per quanto appena affermato, proponiamoci di determinare il polinomio delle radici di ordine
al fine di determinare quello di ordine
. Sia
un elemento di ordine
allora tutti gli altri elementi di pari ordine si esprimeranno come
con
e
, ricordiamo, è numero primo maggiore di
. Esse saranno pertanto
e se ad esse aggiungiamo l'elemento
allora sappiamo che esse sono le radici dell'equazione
![{\displaystyle x^{q}-1\equiv 0{\pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4bed03cdd0733100c1183a17fee8ed8719e26e9)
che sappiamo fattorizzare in:
![{\displaystyle x^{q}-1\equiv (x-1)(x^{q-1}+x^{q-2}+\ldots +x^{2}+x+1){\pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb23d1dabbf785f482af1ca4558b1b1968afa2d2)
è immediato rilevare che
![{\displaystyle p_{q}(x)\equiv x^{q-1}+x^{q-2}+\ldots +x^{2}+x+1{\pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84ce51abc9ca9f52a65ed6118846fc8e08d4d700)
e per quanto detto prima otteniamo:
![{\displaystyle p_{2q}(x)\equiv x^{q-1}-x^{q-2}+\ldots +x^{2}-x+1{\pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14b716532f0c8bb453b1512de7dcfe9b1ee8c898)
che è il polinomio delle radici primitive.