Pour télécharger le mémoire du TIPE : cliquez ici

INTRODUCTION : Les outils permettant de générer de telles suites ont pu être élaborés grâce à l'étude de suites, ce qui les place dans le cadre des systèmes dynamiques discrets.
    Dans l'usage courant, ces générateurs se retrouvent dans la plupart des logiciels de calcul et de programmation (généralement sous le terme anglais "random"), et, pour être ainsi implantés sous forme algorithmique, ont nécessairement été mathématiquement formalisés. De ce fait, le caractère aléatoire d'un générateur est très relatif : les nombres qu'il renvoie semblent pris au hasard, car ils ne répondent à aucune logique de choix évidente. En réalité, les suites sont guidées par des fonctions de récurrence. Et ces générateurs sont donc dénommés Générateurs de Nombres Pseudo-Aléatoires (GNPA).

Notre objectif est double :
- considérer cet outil sous son aspect mathématique, et les diverses conséquences qui en découlent
- mettre en évidence l'intérêt de cet outil et les possibilités qu'il développe dans la théorie des systèmes dynamiques.

- ETUDE -
  • Présentation des GNPA
    Les suites de nombres dites aléatoires sont utilisées dans de nombreux domaines, pour des tests statistiques (en économie, industrie, informatique, ..., où ils permettent notamment de s'assurer de certains faits en effectuant des prises de données de manière aléatoire sur un ensemble qui ne pourrait être étudié totalement), en cryptographie, dans tous les simulateurs (afin d'amener l'utilisateur à réagir face à des situations imprévues), dans les jeux informatiques, et dans la théorie des objets fractals (voir troisième partie).
    On a donc créé des algorithmes informatiques capables de former très rapidement des suites aléatoires de grande longueur, constituées généralement soit d'entiers sur un intervalle borné de N, soit de réels entre 0 et 1. (On verra cependant en troisième partie certains problèmes apparaissant lors de la création de suites aléatoires sur un intervalle borné de R.)
    Les premiers GNPA sont apparus aux débuts de l'informatique, dans les années 1950. Leur principe était particulièrement simple, et ne possédait pas de justification mathématique : le générateur recevait un nombre à quatre chiffres, initialisé par une horloge, puis ce nombre était élevé au carré. On prenait alors les deux premiers et les deux derniers chiffres du nombre obtenu, puis ceux-ci étaient concaténés pour former un nouveau nombre à quatre chiffres. Après un certain nombre d'itérations de ce processus, le caractère aléatoire de ce générateur prenait forme : deux nombres initiaux très légèrement dissemblables donnaient des résultats complètement différents (on se trouvait donc face à un phénomène chaotique non négligeable).
    Ce principe est rapidement tombé en désuétude : le besoin, lors d'un test statistique, d'un très grand nombre de nombres aléatoires rendait prohibitif le temps d'initialisation (il était nécessaire d'attendre que l'horloge change d'affichage...). Il est donc devenu nécessaire de chercher un autre processus d'initialisation, ou bien de reconsidérer les données du problème.
    La quasi-totalité des GNPA utilisés à l'heure actuelle sont des algorithmes adaptés aux structures de calcul des processeurs informatiques, lesquels permettent facilement les opérations congruentielles. On obtient donc des suites de la forme :
Un+1 = f ( Un ) [M]
avec Uo dans [[0 , M-1]]. Ces GNPA sont très rapides, ne dépendent pas de paramètres physiques ( ce qui permet de retrouver les mêmes résultats si la suite est initialisée de la même manière ), et sont pour la plupart suffisants en terme de caractère aléatoire.
 
    Les GNPA les plus utilisés à l'heure actuelle sont les générateurs linéaires congruentiels, pour lesquels la fonction f de récurrence est une fonction affine. Une suite de termes renvoyée par un tel générateur est donc de la forme :
Un+1 = A.Un + C [M]
où A , C , M sont trois entiers naturels non nuls et Uodans [[0 , M-1]]

On dispose en outre dans ce cas d'un théorème prouvé par Hull-Dobell (1962), donnant une condition nécessaire et suffisante pour que la suite de termes renvoyée par un générateur linéaire congruentiel décrive un cycle sur l'ensemble des valeurs de
[[0 , M-1]] : il faut et il suffit que les trois conditions suivantes soient remplies :
 

C est premier avec M 
pour tout P entier naturel premier, si P divise M, P divise (A-1) 
si 4 divise M, 4 divise (A-1) 
On rencontre aussi parfois le générateur RSA, pour lequel la fonction de récurrence est une fonction puissance entière, mais on ne connaît pas de théorème équivalent à celui de Hull-Dobell s'y appliquant. Quant au BBS (générateur de Blum-Blum-Shub), pour lequel la fonction de récurrence est le carré, on sait qu'il ne peut obtenir que des résidus quadratiques, donc il ne peut y avoir de cycle sur tous les entiers inférieurs au modulo.
 
  • Fiabilité d'un GNPA
  Ce qu'on attend d'un GNPA

Le besoin toujours plus grand de suites aléatoires de longueur importante a entraîné l'abandon de certains GNPA devenus obsolètes par la lenteur de leurs calculs, le nombre limité des valeurs qu'ils pouvaient renvoyer, une trop grande irrégularité dans la répartition des valeurs (comme par exemple si la modélisation d'un lancer de dé renvoyait un 6 une fois sur deux), ou encore une trop grande régularité (dans l'exemple ci-dessus, un GNPA trop régulier renverrait en 6 lancers les six faces du dé, événement qui, statistiquement parlant) n'a en fait qu'une probabilité de 1/60 environ). Ces deux derniers défauts peuvent être décelés à l'aide de fonctions de test sur un échantillon de valeurs renvoyées par un GNPA donné.

  Mesure de la qualité d'un GNPA

                Le test Khi-deux

                Les tests multidimensionnels

                      Le test de Kolmogorov-Smirnoff

  Amélioration du caractère aléatoire
 

  • GNPA généralisés, applications
GNPA à valeurs dans un segment I non vide non réduit à un point de R

Les GNPA étant des systèmes dynamiques discrets, ils ne peuvent rendre compte d'un phénomène continu qu'en approximation. En effet, en pratique, l'ensemble U des valeurs d'une suite renvoyée par un GNPA est fini, ce qui n'est pas le cas de I.
    On ramène donc, en approximation, la génération aléatoire dans un intervalle borné de R à la génération d'une suite à valeurs dans un ensemble fini.
    On peut alors travailler avec un Générateur de Nombres Aléatoire Idéal dans [0 , 1].

GNPA à valeurs dans un ensemble non borné

Illustration avec les objets fractals de Mandelbrot

CONCLUSION : Relativement récents, les Générateurs de Nombres Pseudo-Aléatoires forment un outil puissant et sûr. Principalement utilisés dans l'étude de phénomènes liés au hasard, ils constituent le seul moyen de modéliser géométriquement des figures à caractère chaotique. En particulier, la géométrie fractale s'appuie essentiellement sur la génération aléatoire pour visualiser ses modèles. Après une importante évolution lors de la mise au point des générateurs congruentiels, les GNPA n'ont plus été sujets à de grands bouleversements théoriques. Et, si leur utilisation s'étendra et prendra de l'importance, il est probable qu'ils ne subiront plus d'évolution majeure dans l'avenir.
 

- SOURCES D'INFORMATION -
  •   Divers ouvrages parmi lesquels :
    • Les objets fractals, Benoît Mandelbrot, éd. Champs Flammarion, 1995.
    • Cryptographie, théorie et pratique, Douglas Stinson, éd. International Thomson Publishing France, 1996.
    • Les lois du chaos, Ilya Prigogine, éd. Champs Flammarion, 1997.
    • Les systèmes dynamiques discrets, François Robert, éd. Springer.
    • Introduction à la statistique, Emile Amzallag, Norbert Piccioli et François Bry, éd. Hermann, 1978.
     
  • Internet, et notamment les sites