Generatore (teoria dei numeri)

Da Wikipedia, l'enciclopedia libera.

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

I generatori modulo rivestono un'importanza considerevole in crittografia.

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

sono le classi di congruenza di , , , , e .

Si ha che è un generatore modulo , perché 32 = 9, 33 = 13, 34 = 11, 35 = 5 e 36 = 1 (modulo 14). L'unica altra radice primitiva modulo è .

Trovare i generatori[modifica | modifica wikitesto]

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

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 .

Dimostrazione dell'esistenza di un generatore modulo pk, p dispari[modifica | modifica wikitesto]

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

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

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

ovvero

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

Questa quantità è uguale a se e solo se è divisibile per ; tuttavia, se lo fosse, si avrebbe

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.

Funzioni simmetriche delle radici primitive modulo p[modifica | modifica wikitesto]

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

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

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

basta calcolare la sommatoria degli elementi di ordine e moltiplicare tale valore per l'"indice di restrizione" . Quindi

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:

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:

Considerando ora il polinomio monico delle radici primitive modulo (primo e diverso da ) esso sarà di grado :

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:

Riportiamo alcuni esempi di tali polinomi:

  • (per questo non si può impiegare l'Art.80 di Gauss, ma si è solo verificato "a mano")

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

Infatti se è un primo di Fermat esso è del tipo ed il numero delle radici primitive sarà

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 è

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

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

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

che sappiamo fattorizzare in:

è immediato rilevare che

e per quanto detto prima otteniamo:

che è il polinomio delle radici primitive.

Note[modifica | modifica wikitesto]

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

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

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