In un'aritmetica modulare di ordine $N$ si possono dare particolari numeri $g$ detti generatori; un generatore è una base che successivamente elevata a potenza, genera tutti i numeri che sono primi con $N$.

Non è detto che un generatore esista; per esempio in un'aritmetica modulo $12$, tipo aritmetica dell'orologio, non c'è alcun generatore, come si può verificare facilmente a mano, o con lo strumento qui a destra. Solo $5, 7, 11$ sono primi con $12$ e tutti i numeri minori di $12$ innestano cicli brevi che generano troppi pochi numeri.

Ne consegue che se $N$ è primo allora $g$ genererà successivamente tutti i numeri minori di $N$.

Si può dimostrare che se $N$ è primo allora esiste sempre almeno un generatore $g$; per quanto detto sopra $g$ genererà successivamente tutti i numeri minori di $N$.

Per esempio se $N = 17$, $2$ non è generatore, mentre $3$ e $5$ lo sono.

Nel riquadro a destra è possibile verificare questi esempi e anche cercare un generatore, dato il modulo dell'aritmetica. Sono accettati valori fino a 255.

Applicazioni

I generatori sono usati tra l'altro nell'algoritmo Diffie-Helman.