Le développement historique

La « pré-histoire » (avant 1940) :  les premières suites des variables aléatoires étaient générées par des dispositifs analogiques. Les fluctuations de tension aux bords d'une résistance électrique chauffée alimentée par un courant stabilisé sont bien modélisées par un bruit blanc. Les instants où des coups sont enregistrés par un compteur de rayonnement cosmique suivent une loi exponentielle. Ces phénomènes ont été exploités pour créer des tables des variables aléatoires [#!RAND!#]. L'avènement des premiers ordinateurs numériques, a rendu ces méthodes impraticables. D'une part, le stockage sur les premières machines des tables des variables aléatoires occupait beaucoup de mémoire (très chère à l'époque) et, d'autre part, le couplage direct des dispositifs analogiques aux ordinateurs numériques avait l'inconvénient de fournir des suites non reproductibles des nombres au hasard.

La « proto-histoire » (1940-1950) :  il est apparu que la génération algorithmique des suites des nombres au hasard était plus efficace. Plusieurs algorithmes ont été proposés pour engendrer de telles suites. Par exemple

1. la suite des digits successifs des nombres transcendants. Si
   
   
   
   est la représentation en base ^2.1 de la partie fractionnaire de (on note la partie entière), on sait que pour Lebesgue-presque tout nombre transcendant , la suite de ses digits est une suite équi-distribuée ([#!Bil!#], théorème 1.2) sur . Le problème est que pour un transcendant donné on ignore si ceci est vrai. On ignore même si pour les décimaux du nombre , par exemple, la quantité
   
   
   
   tend vers 1/10 pour tout [#!MetRosRosTelTel!#].
2. la méthode de « Procuste »^2.2qui consiste, en partant d'un nombre entier à digits (en base de 10 par exemple) , de prendre son carré et de former un nouvel entier en ne gardant que les digits du milieu . Cette méthode proposée par [#!Neu!#] donne une suite d'entiers avec des propriétés statistiques très mauvaises [#!For!#] et a été vite abandonnée.
3. mélange aléatoire des méthodes connues. Il s'agit d'une méthode qui tente de combiner de manière aléatoire les méthodes précédentes pour fournir une « meilleure » suite aléatoire. Il a été démontré qu'en absence d'une théorie, une telle méthode peut être très dangereuse (cf. Algorithme K dans Vol. 2, page 4 de [#!Knu!#]). Dans la quête du « toujours plus », on s'est aperçu que l'arithmétique ne manque pas ...d'humour.

Si les premières méthodes algorithmiques n'ont pas résolu le problème de génération de nombres au hasard, elles ont eu le mérite d'introduire une nouvelle problématique. Il est apparu en effet que l'algorithmique ne fournit pas des suites aléatoires mais des suites déterministes qui se comportent comme des suites aléatoires dans le sens que leurs propriétés statistiques pertinentes sont similaires à celles des suites aléatoires [#!Rip!#]. On parle alors de nombres pseudo-aléatoires.

Les « temps modernes » (après 1950) :  L'essor des ordinateurs digitaux a imposé des algorithmes simples et rapides pour la génération des nombres pseudo-aléatoires. Les premiers résultats de la théorie ergodique de systèmes dynamiques sont aussi disponibles ce qui incite à utiliser des transformations ergodiques du cercle, ou plus précisement leurs contre-partie discrète, pour engendrer des suites pseudo-aléatoires. Les méthodes les plus utilisées de nos jours sont

1. la méthode de récurrence congruentielle affine de rang 1[#!Leh!#] qui consiste à fixer des constantes positives , et appelées respectivement multiplicateur, accroissement et module ainsi que la valeur initiale , appelée racine du générateur et à considérer la suite des entiers , donnés par la récurrence
   
   
   

2. la méthode de récurrence congruentielle affine de rang [#!Fra!#,#!Wat!#] consiste à fixer le module , les paramètres et le paramètre ainsi que les valeurs initiales du générateur et à considérer la suite, pour ,
   
   
   
   Le cas particulier nous ramène au cas précédent. Le cas particulier , et , connu sous le nom de générateur de Fibonacci, se comporte comme la suite congruentielle affine avec et a des propriétés statistiques très mauvaises. Celles-là s'améliorent au fur et à mesure que augmente.
3. la méthode de décalage du registre dérive de la méthode précédente (avec ) dans le sens qu'une méthode de récurrence congruentielle affine de rang est appliquée non pas aux nombres eux mêmes mais sur les digits de leur représentation binaire.
4. la méthode de Fibonnaci lacunaire où l'on fixe deux lacunes et avec et racines et on construit la suite
   
   
   
   avec représentant une opération binaire (par exemple l'addition modulo ).