Générateur

Il s'agit du générateur le plus utilisé de nos jours. On sait que sa période est strictement inférieure à et les théorèmes suivants ([#!Rip!#], pp. 20-22) nous donnent les conditions sous lesquelles on obtient la maximisation de la période.

La dernière partie de ce théorème est due à [#!Tho!#] et répond à une vieille querelle qui opposait les partisans des générateurs avec et de ceux -- supposés moins performants -- avec .

Il peut s'avérer difficile de trouver les racines primitives. Mais si une telle racine est trouvée, toutes les autres sont obtenues en vertu du

On voit que la factorisation en nombres premiers de joue un rôle important. Le tableau donne les facteurs premiers de pour quelques valeurs choisies de .

	Factorisation première de
15
16
30
31
32
33
60
63
64

Les valeurs des paramètres recommandées par [#!LewGooMil!#] sont et . On vérifie à l'aide du tableau précédent que est premier et que 7 est une racine primitive de . Ce générateur est utilisé par plusieurs bibliothèques des programmes installées sur des ordinateurs divers puisqu'il possède de bonnes propriétés statistiques. Son écriture algorithmique est

La programmation de cet algorithme présente certaines difficultés sur les ordinateurs actuels (à architecture de 32 bits). En effet, les entiers qui apparaissent peuvent être aussi grands que qui ne sont pas représentables par des entiers-machine de 32 bits. Quelques astuces sont donc nécessaires pour programmer correctement cet algorithme; deux de ces astuces sont proposées dans le paragraphe d'exercices. Un bon test de l'implémentation informatique de cet algorithme consiste à l'initialiser avec ; la 10000e itérée doit alors être .