Generatore (teoria dei numeri)

Da Wikipedia, l'enciclopedia libera.

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 Zn*. Esso è un gruppo ciclico se e solo se n è uguale a 2, 4, pk o 2 pk 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 Zn*. 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é 32 = 9, 33 = 13, 34 = 11, 35 = 5 e 36 = 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 p1,...,pk. Ora, per ogni elemento m di (Z/nZ)×, calcolare
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 p0 tali che, per ogni primo pp0, esiste un generatore modulo p minore di

C p1/4+ε.

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

70 (ln(p))2.

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

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

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 p2, 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 p2 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 p2; 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 ap-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 p2.

Per dimostrare la proposizione per pk, con k>2, si procede per induzione: supponiamo che a sia una radice primitiva per tutti i pj con j<k. In particolare,

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

ovvero

a^{\phi(p^{k-2})}=1+lp^{k-2}

per un qualche l. Questa relazione vale anche modulo pk; inoltre l'ordine di a modulo pk deve essere un multiplo di \phi(p^{k-1}), perché ha quest'ordine modulo pk-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 pk-1 sia \phi(p^{k-1}). Questo è assurdo, e quindi l'ordine di a modulo pk è esattamente \phi(p^k), e a è una radice primitiva modulo pk. Per induzione questo è valido per ogni k.

L'estensione ai numeri nella forma 2pk segue immediatamente, perché il gruppo moltiplicativo di questo anello contiene lo stesso numero di elementi di quello dell'anello di pk elementi, ed esiste una corrispondenza biunivoca che conserva le operazioni (ossia un isomorfismo) tra questi due gruppi.

Note[modifica | modifica sorgente]

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

Bibliografia[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

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