250
8 G´ en´ erateurs de nombres al´ eatoires
Les nombres de cette suite sont
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
0,10000 2 = 2
−1 =
1
2 = 0,5,
0,00101 2 = 2
−3 + 2
−5 = 0,15625,
0,11110 2 = 2
−1 + 2
−2 + 2
−3 + 2
−4 = 0,9375,
0,01001 2 = 2
−2 + 2
−5 = 0,28125,
0,01001 2 = 2
−2 + 2
−5 = 0,28125,
0,11011 2 = 2
−1 + 2
−2 + 2
−4 + 2
−5 = 0,84375,
la derni` ere ´ ecriture ´ etant l’´ ecriture d´ ecimale.
Qu’est-ce qu’un bon g´ en´ erateur de nombres al´ eatoires ? `
A quels crit` eres doit-il satisfaire ? Lorsqu’on lance une pi` ece plusieurs fois, le r´ esultat de chaque lancer est
ind´ ependant des pr´ ec´ edents, et chacun des deux r´ esultats possibles a une probabilit´ e
de
1
2 . Cela a comme cons´ equence que, si on lance un grand nombre de fois, on devrait
avoir PILE (not´ e 0) une fois sur deux ` a peu pr` es et FACE (not´ ee 1) environ une fois
sur deux : c’est la loi des grands nombres. Si notre exp´ erience consiste plutˆ ot ` a lancer
la pi` ece deux fois, on a quatre r´ esultats possibles :
00 01 10 11.
Si on r´ ep` ete souvent cette exp´ erience de deux lancers cons´ ecutifs, on s’attend ` a obtenir
chaque r´ esultat environ une fois sur quatre. De mˆ eme, si l’exp´ erience consiste ` a lancer
la pi` ece trois fois, on a 2
3 = 8 r´ esultats possibles ´ equiprobables :
000 001 010 011 100 101 110 111.
Dans le cas d’un g´ en´ erateur de nombres al´ eatoires, on voudrait que les mˆ emes propri´ et´ es soient respect´ ees. Pour v´ erifier que les g´ en´ erateurs de nombres al´ eatoires que
l’on construit ont bien ces propri´ et´ es, on les soumet ` a une batterie de tests statistiques.
Tous les g´ en´ erateurs de nombres pseudo-al´ eatoires sont des algorithmes qui g´ en` erent
des suites p´ eriodiques de nombres ` a partir de conditions initiales en nombre fini.
Penchons-nous sur ces suites.
D´ efinition 8.1 Une suite {a n } n≥0 est p´ eriodique s’il existe un entier M > 0 tel que,
pour tout n ∈ N, a n = a n+M . Le nombre N > 0 minimum ayant cette propri´ et´ e est
appel´ e la p´ eriode de la suite. Lorsqu’on voudra mettre l’accent sur cette propri´ et´ e, on
pourra, `
a l’occasion, appeler N la p´ eriode minimale de la suite.
Lemme 8.2 Soit {a n } n∈N∪{0} une suite p´ eriodique de p´ eriode minimale N et soit M ∈
N tel que, pour tout n ∈ N, a n = a n+M . Alors, N divise M .
Preuve Divisons M par N : il existe des entiers q et r tels que M = qN + r et
0 ≤ r < N. Montrons que, pour tout n, on a a n = a n+r .
En effet,
8 G´ en´ erateurs de nombres al´ eatoires
Les nombres de cette suite sont
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
0,10000 2 = 2
−1 =
1
2 = 0,5,
0,00101 2 = 2
−3 + 2
−5 = 0,15625,
0,11110 2 = 2
−1 + 2
−2 + 2
−3 + 2
−4 = 0,9375,
0,01001 2 = 2
−2 + 2
−5 = 0,28125,
0,01001 2 = 2
−2 + 2
−5 = 0,28125,
0,11011 2 = 2
−1 + 2
−2 + 2
−4 + 2
−5 = 0,84375,
la derni` ere ´ ecriture ´ etant l’´ ecriture d´ ecimale.
Qu’est-ce qu’un bon g´ en´ erateur de nombres al´ eatoires ? `
A quels crit` eres doit-il satisfaire ? Lorsqu’on lance une pi` ece plusieurs fois, le r´ esultat de chaque lancer est
ind´ ependant des pr´ ec´ edents, et chacun des deux r´ esultats possibles a une probabilit´ e
de
1
2 . Cela a comme cons´ equence que, si on lance un grand nombre de fois, on devrait
avoir PILE (not´ e 0) une fois sur deux ` a peu pr` es et FACE (not´ ee 1) environ une fois
sur deux : c’est la loi des grands nombres. Si notre exp´ erience consiste plutˆ ot ` a lancer
la pi` ece deux fois, on a quatre r´ esultats possibles :
00 01 10 11.
Si on r´ ep` ete souvent cette exp´ erience de deux lancers cons´ ecutifs, on s’attend ` a obtenir
chaque r´ esultat environ une fois sur quatre. De mˆ eme, si l’exp´ erience consiste ` a lancer
la pi` ece trois fois, on a 2
3 = 8 r´ esultats possibles ´ equiprobables :
000 001 010 011 100 101 110 111.
Dans le cas d’un g´ en´ erateur de nombres al´ eatoires, on voudrait que les mˆ emes propri´ et´ es soient respect´ ees. Pour v´ erifier que les g´ en´ erateurs de nombres al´ eatoires que
l’on construit ont bien ces propri´ et´ es, on les soumet ` a une batterie de tests statistiques.
Tous les g´ en´ erateurs de nombres pseudo-al´ eatoires sont des algorithmes qui g´ en` erent
des suites p´ eriodiques de nombres ` a partir de conditions initiales en nombre fini.
Penchons-nous sur ces suites.
D´ efinition 8.1 Une suite {a n } n≥0 est p´ eriodique s’il existe un entier M > 0 tel que,
pour tout n ∈ N, a n = a n+M . Le nombre N > 0 minimum ayant cette propri´ et´ e est
appel´ e la p´ eriode de la suite. Lorsqu’on voudra mettre l’accent sur cette propri´ et´ e, on
pourra, `
a l’occasion, appeler N la p´ eriode minimale de la suite.
Lemme 8.2 Soit {a n } n∈N∪{0} une suite p´ eriodique de p´ eriode minimale N et soit M ∈
N tel que, pour tout n ∈ N, a n = a n+M . Alors, N divise M .
Preuve Divisons M par N : il existe des entiers q et r tels que M = qN + r et
0 ≤ r < N. Montrons que, pour tout n, on a a n = a n+r .
En effet,