260
8 G´ en´ erateurs de nombres al´ eatoires
d´ emarrage du programme ? Doit-on laisser les machines de keno ´ eternellement allum´ ees ?
Et comment font les jeux vid´ eos ? Voici deux solutions assez communes. La premi` ere
fa¸ con n´ ecessite que l’appareil soit ´ eteint « convenablement ». Si on l’´ eteint en pressant
le bouton d’allumage (et non en d´ ebranchant le cˆ able d’alimentation ´ electrique), l’appareil enregistre, juste avant de s’´ eteindre, les derniers a i qu’il vient de g´ en´ erer sur un
disque ou une carte-m´ emoire ; ils serviront alors comme conditions initiales au prochain
allumage. La deuxi` eme solution suppose qu’une horloge soit int´ egr´ ee aux circuits de l’appareil. Au d´ emarrage, le programme demande le nombre de secondes (ou de milli` emes
de secondes) ´ ecoul´ e depuis une date fix´ ee, disons depuis minuit le 1
er janvier de l’an
2000. Les derni` eres d´ ecimales de ce nombre seront utilis´ ees comme conditions initiales.
8.3.3 Le cas g´ en´ eral
Ici, nous supposerons que le lecteur connaˆ ıt le corps F p r (voir, par exemple, la section 6.5 du chapitre 6).
D´ efinition 8.14 1. Soit p un entier premier. Un g´ en´ erateur de nombres al´ eatoires
F p -lin´ eaire est un g´ en´ erateur de la forme
a n = q 0 a n−r + q 1 a 1 + · · · + q r−1 a n−1 (mod p),
(8.6)
o` u les q 0 , . . . , q r−1 et les conditions initiales a 0 , . . . , a r−1 sont des entiers de
{0, 1, . . . , p − 1}, et les op´ erations sont celles de F p , c’est-` a-dire modulo p.
2. Un g´ en´ erateur r´ ecursif multiple est d´ efini par la r´ ecurrence lin´ eaire
a n = q 0 a n−r + q 1 a 1 + · · · + q r−1 a n−1 (mod p),
u n =
an
p .
On voit que, si on prend p = 2, alors un g´ en´ erateur de nombres al´ eatoires F 2 -lin´ eaire
est simplement un registre `
a d´ ecalage. Un g´ en´ erateur de nombres al´ eatoires F p -lin´ eaire
g´ en` ere des nombres al´ eatoires a n ∈ {0, 1, . . . , p − 1}, alors que le g´ en´ erateur r´ ecursif
multiple associ´ e g´ en` ere des nombres al´ eatoires u n ∈ [0, 1].
Les th´ eor` emes 8.9 et 8.13 se g´ en´ eralisent ` a un g´ en´ erateur F p -lin´ eaire. Dans le cas de
F 2 , le fait de travailler modulo le polynˆ ome Q(x) donn´ e en (8.5) permet d’´ ecrire
x
r = q 0 + q 1 x + · · · + q r−1 x
r−1
(8.7)
parce que q i = −q i . Comme ceci n’est plus vrai dans F p , il faut adapter le polynˆ ome
Q(x) pour que la relation (8.7) reste valable.
Th´ eor` eme 8.15 Si p est premier et que q 0 , . . . , q r−1 ∈ {0, 1, . . . , p− 1} sont choisis tels
que le polynˆ ome
Q(x) = x
r
− q r−1 x
r−1
− · · · − q 1 x − q 0
8 G´ en´ erateurs de nombres al´ eatoires
d´ emarrage du programme ? Doit-on laisser les machines de keno ´ eternellement allum´ ees ?
Et comment font les jeux vid´ eos ? Voici deux solutions assez communes. La premi` ere
fa¸ con n´ ecessite que l’appareil soit ´ eteint « convenablement ». Si on l’´ eteint en pressant
le bouton d’allumage (et non en d´ ebranchant le cˆ able d’alimentation ´ electrique), l’appareil enregistre, juste avant de s’´ eteindre, les derniers a i qu’il vient de g´ en´ erer sur un
disque ou une carte-m´ emoire ; ils serviront alors comme conditions initiales au prochain
allumage. La deuxi` eme solution suppose qu’une horloge soit int´ egr´ ee aux circuits de l’appareil. Au d´ emarrage, le programme demande le nombre de secondes (ou de milli` emes
de secondes) ´ ecoul´ e depuis une date fix´ ee, disons depuis minuit le 1
er janvier de l’an
2000. Les derni` eres d´ ecimales de ce nombre seront utilis´ ees comme conditions initiales.
8.3.3 Le cas g´ en´ eral
Ici, nous supposerons que le lecteur connaˆ ıt le corps F p r (voir, par exemple, la section 6.5 du chapitre 6).
D´ efinition 8.14 1. Soit p un entier premier. Un g´ en´ erateur de nombres al´ eatoires
F p -lin´ eaire est un g´ en´ erateur de la forme
a n = q 0 a n−r + q 1 a 1 + · · · + q r−1 a n−1 (mod p),
(8.6)
o` u les q 0 , . . . , q r−1 et les conditions initiales a 0 , . . . , a r−1 sont des entiers de
{0, 1, . . . , p − 1}, et les op´ erations sont celles de F p , c’est-` a-dire modulo p.
2. Un g´ en´ erateur r´ ecursif multiple est d´ efini par la r´ ecurrence lin´ eaire
a n = q 0 a n−r + q 1 a 1 + · · · + q r−1 a n−1 (mod p),
u n =
an
p .
On voit que, si on prend p = 2, alors un g´ en´ erateur de nombres al´ eatoires F 2 -lin´ eaire
est simplement un registre `
a d´ ecalage. Un g´ en´ erateur de nombres al´ eatoires F p -lin´ eaire
g´ en` ere des nombres al´ eatoires a n ∈ {0, 1, . . . , p − 1}, alors que le g´ en´ erateur r´ ecursif
multiple associ´ e g´ en` ere des nombres al´ eatoires u n ∈ [0, 1].
Les th´ eor` emes 8.9 et 8.13 se g´ en´ eralisent ` a un g´ en´ erateur F p -lin´ eaire. Dans le cas de
F 2 , le fait de travailler modulo le polynˆ ome Q(x) donn´ e en (8.5) permet d’´ ecrire
x
r = q 0 + q 1 x + · · · + q r−1 x
r−1
(8.7)
parce que q i = −q i . Comme ceci n’est plus vrai dans F p , il faut adapter le polynˆ ome
Q(x) pour que la relation (8.7) reste valable.
Th´ eor` eme 8.15 Si p est premier et que q 0 , . . . , q r−1 ∈ {0, 1, . . . , p− 1} sont choisis tels
que le polynˆ ome
Q(x) = x
r
− q r−1 x
r−1
− · · · − q 1 x − q 0