Générateur congruentiel linéaire

Un générateur congruentiel linéaire est un générateur de nombres pseudo-aléatoires dont l'algorithme, introduit en 1948 par Derrick Lehmer, sous une forme réduite, pour produire des nombres aléatoires, est basé sur des congruences et une fonction affine. Les nombres pseudo aléatoires forment une suite dont chaque terme dépend du précédent, selon la formule : où a est le multiplicateur, c l'incrément et m le module. Le terme initial est appelé la graine (seed en anglais). C'est elle qui va permettre de générer une suite apparemment aléatoire. Pour chaque graine, on aura une nouvelle suite. Cependant, il est possible que certaines graines permettent d'obtenir une suite plus aléatoire que d'autres. Du fait de l'opération mod (reste dans la division euclidienne de par m), les termes de cette suite sont compris entre 0 et . De plus, comme chaque terme dépend entièrement du précédent, si un nombre apparaît une deuxième fois, toute la suite se reproduit à partir de ce nombre. Or le nombre de valeurs que le nombre peut prendre étant fini (égal à m), la suite est amenée à se répéter au bout d'un certain temps. On dit qu'elle est ultimement périodique. Dans ce type d'algorithme, la qualité du générateur va entièrement dépendre du choix de a, c et m car on ne peut pas se satisfaire d'un générateur qui produit des suites plus ou moins aléatoires, sans aucune raison apparente, selon le choix de X0. Choisir les valeurs a, c et m « au hasard » n'est pas une bonne idée. Prenons un exemple, soit le générateur congruentiel linéaire employant les valeurs a = 25, c = 16, m = 256, nous obtenons : avec X0 = 125, la suite : avec X0 = 96, la suite : avec X0 = 50, la suite : avec X0 = 10, la suite : Il est clair que ces suites ne peuvent être considérées comme aléatoires. On voit donc bien que l'on doit choisir avec précaution les paramètres du générateur si l'on espère obtenir des nombres qui s'approchent de l'aléa parfait. Il faut alors se demander comment choisir a, c et m convenablement.