Primi e generatori di numeri pseudocasuali
Naturalmente non è possibile con un computer ordinario - macchina deterministica per eccellenza - generare numeri veramente casuali (qualsiasi cosa ciò voglia dire). E' però possibile generare successioni di numeri pseudocasuali.
Esiste sull'argomento una enorme letteratura.
Moltissimi generatori lavorano modulo p, dove p è un numero primo. Uno dei primi è di Lehmer (1949) :
xn = a xn-1 + b mod p
Questo generatore ha periodo massimo (conseguibile) p. Di qui l'importanza di avere numeri primi grandi.
Ora sono molto usati i generatori inversivi, dove viene ogni volta calcolato l'inverso i(y) di y, modulo p:
xn = a i(xn-1) + b mod p
Recentemente (1997) Makoto Matsumoto e Takuji Nishimura hanno sviluppato un generatore estremamente efficace, detto Mersenne Twister, il cui periodo è il primo di Mersenne 219937 - 1