Generatore (teoria dei numeri)

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 generatoriModifica

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 dispariModifica

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 pModifica

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.

NoteModifica

BibliografiaModifica

Voci correlateModifica

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