Générateur congruentiel simple et périodicité d'une suite pseudo-aléatoire

Terminale Technologique · Mathématiques STI2D Terminale

À retenir

• u_n+1 = (a u_n + c) m : le terme suivant ne dépend que du précédent. • Il n'y a que m valeurs possibles : la suite est périodique, de période m. • Une période maximale ne suffit pas : il faut aussi tester l'indépendance des termes. • La part de tirages consécutifs croissants doit approcher 50\ \%. • La période de Lehmer vaut m-1 pour m premier ; un module trop petit est rédhibitoire.

Le cours

1. La règle la plus ancienne Le générateur congruentiel linéaire (LCG) applique à chaque étape une règle unique, qui ne dépend que de l'entier précédent : u_n+1 = (a \ u_n + c) \ m \ \et l'on travaille avec _n/m \ [0\\,;\\,1[ Les paramètres m, a, c et u_0 sont entiers, avec 0 a m et 0 \ c m. Tous les termes sont donc des entiers de 0 à m-1 : il existe au plus m valeurs possibles, et la suite est périodique. La période, qui peut être inférieure à m, est la longueur exacte du cycle parcouru avant de revenir au point de départ. Une suite de période 4 n'apporte que quatre valeurs différentes, quel que soit le nombre de tirages : c'est le défaut rédhibitoire de ce générateur. 2. Cinq suites réellement calculées def lcg(m, a, c, u, n): suite = [] for _ in range(n): suite.append(u) u = (a * u + c) % m return suite print(lcg(8, 3, 1, 0, 9)) # [0, 1, 4, 5, 0, 1, 4, 5, 0] periode 4 print(lcg(8, 5, 1, 0, 9)) # [0, 1, 6, 7, 4, 5, 2, 3, 0] periode 8 print(lcg(1000, 1, 1, 1, 7)) # [1, 2, 3, 4, 5, 6, 7] periode 1000 macSuite des u_nPériode 8310\\,;\\,1\\,;\\,4\\,;\\,54 8320\\,;\\,22 8510\\,;\\,1\\,;\\,6\\,;\\,7\\,;\\,4\\,;\\,5\\,;\\,2\\,;\\,38 1000111\\,;\\,2\\,;\\,3\\,;\\,4\\,;\\,5\\,;\\,6\\,;\\,71000 2\\,147\\,483\\,6471680701\\,;\\,16807\\,;\\,282475249m-1 La dernière ligne est le générateur multiplicatif de Lehmer, à c = 0 : pour un module premier, la période maximale vaut m - 1, soit près de 2,1 milliards de valeurs. La deuxième ligne montre qu'une période peut être ridiculement courte alors que m = 8 : la règle (3u + 2) \ 8 ne fait produire que 0 et 2. 3. Méthode : les trois tests d'un générateur 1. Test de période : on parcourt les valeurs en mémoire jusqu'à retrouver u_0. Si la période est inférieure à N, le générateur est inutilisable. 2. Test d'histogramme : sur 10\\,000 tirages en 10 classes, chaque classe doit contenir environ 1000 valeurs. Attention : ce test est trompeur, un générateur très structuré peut le réussir. 3. Test d'indépendance : on mesure la corrélation entre deux tirages consécutifs, ou la proportion de tirages croissants, qui doit approcher 50\\ \% pour des valeurs indépendantes. GénérateurCorrélation d'ordre 1Part de tirages croissants a=1, c=1, m=10000,993999,9\\ \% a=61, c=7, m=10000,015350,3\\ \% Lehmer, m = 2^31-1-0,001650,2\\ \% générateur de la bibliothèque-0,004449,9\\ \% 4. Pièges • Croire qu'une période maximale garantit un bon aléa : avec a = 1 et c = 1, la période vaut m = 1000 et l'histogramme est parfaitement plat, mais 99,9\\ \% des valeurs croissent. L'histogramme seul ne prouve rien. • Choisir un module trop petit : m = 1000 signifie 1000 valeurs possibles, donc 100 répétitions exactes sur 100\\,000 tirages, quelle que soit la qualité de a et c. Il faut m \ N et, en pratique, des milliards. • Utiliser un LCG pour de la cryptographie : la structure algébrique permet de retrouver les termes. La bibliothèque standard emploie un générateur de Mersenne Twister, de période 2^19937-1,cellent pour la simulation mais non pour le secret.

Dans ce chapitre