256
8 G´ en´ erateurs de nombres al´ eatoires
de grande p´ eriode, nous obtiendrons de meilleurs g´ en´ erateurs en combinant plusieurs
g´ en´ erateurs F p -lin´ eaires de p´ eriodes ind´ ependantes.
Revenons sur le registre ` a d´ ecalage et montrons comment sont choisis les coefficients
pour que la suite g´ en´ er´ ee soit de p´ eriode 2
r
− 1. Quoique cela ne soit pas absolument
n´ ecessaire, il est pr´ ef´ erable d’avoir vu la section 1.4 du chapitre 1 pour lire la preuve de ce
r´ esultat (th´ eor` eme 8.9 ci-dessous). Pour m´ emoire, le corps F p est l’ensemble {0, 1, . . . , p−
1} muni des op´ erations d’addition et de multiplication modulo p. C’est un corps si et
seulement si p est premier.
D´ efinition 8.7 Un polynˆ ome
Q(x) = x
r + q r−1 x
r−1 + · · · + q 1 x + q 0
` a coefficients dans F p est primitif s’il est irr´ eductible et si l’ensemble des ´ el´ ements non
nuls de
F p r = {b 0 + b 1 x + · · · + b r−1 x
r−1
| b i ∈ F p }
peut s’´ ecrire comme
F p r \ {0} = {x
i
| i = 0, . . . , p
r
− 2}
o` u les puissances x
i de x sont prises modulo Q(x).
Exemple 8.8 Prenons p = 2. On va montrer que le polynˆ ome Q(x) = x
3 + x + 1 est
irr´ eductible sur F 2 . En effet, supposons que Q(x) = Q 1 (x)Q 2 (x). Puisque Q(x) est de
degr´ e 3, soit Q 1 (x) soit Q 2 (x) est de degr´ e 1 et appartient ` a l’ensemble {x, x + 1}. Si x
divise Q(x), alors on devrait avoir Q(0) = 0, ce qui n’est pas vrai. Si x + 1 divise Q(x),
alors on devrait avoir Q(1) = 0, ce qui n’est pas vrai non plus. Donc, ni x ni x + 1 ne
divise Q(x). Par cons´ equent, Q(x) est irr´ eductible. Les ´ el´ ements non nuls de F 2 3 sont
donn´ es par {1, x, x + 1, x
2 , x
2 + 1, x
2 + x, x
2 + x + 1}. V´ erifions que ce sont tous des
puissances de x. En effet, Q(x) = 0 donne x
3 = x + 1, donc
x
4 = x(x + 1) = x
2 + x,
x
5 = x(x
2 + x) = x
3 + x
2 = (x + 1) + x
2 = x
2 + x + 1,
x
6 = x(x
2 + x + 1) = x
3 + x
2 + x = (x + 1) + x
2 + x = x
2 + 1,
x
7 = x(x
2 + 1) = x
3 + x = (x + 1) + x = 1.
Th´ eor` eme 8.9 Si les coefficients q 0 , . . . , q r−1 d’un registre `
a d´ ecalage sont choisis tels
que le polynˆ ome
Q(x) = x
r + q r−1 x
r−1 + · · · + q 1 x + q 0
(8.5)
est primitif sur F 2 , alors, pour toute suite (a 0 , . . . , a r−1 ) de conditions initiales, telle
que les a i ne sont pas tous nuls, la suite g´ en´ er´ ee par le registre est p´ eriodique de p´ eriode
2
r
− 1.
8 G´ en´ erateurs de nombres al´ eatoires
de grande p´ eriode, nous obtiendrons de meilleurs g´ en´ erateurs en combinant plusieurs
g´ en´ erateurs F p -lin´ eaires de p´ eriodes ind´ ependantes.
Revenons sur le registre ` a d´ ecalage et montrons comment sont choisis les coefficients
pour que la suite g´ en´ er´ ee soit de p´ eriode 2
r
− 1. Quoique cela ne soit pas absolument
n´ ecessaire, il est pr´ ef´ erable d’avoir vu la section 1.4 du chapitre 1 pour lire la preuve de ce
r´ esultat (th´ eor` eme 8.9 ci-dessous). Pour m´ emoire, le corps F p est l’ensemble {0, 1, . . . , p−
1} muni des op´ erations d’addition et de multiplication modulo p. C’est un corps si et
seulement si p est premier.
D´ efinition 8.7 Un polynˆ ome
Q(x) = x
r + q r−1 x
r−1 + · · · + q 1 x + q 0
` a coefficients dans F p est primitif s’il est irr´ eductible et si l’ensemble des ´ el´ ements non
nuls de
F p r = {b 0 + b 1 x + · · · + b r−1 x
r−1
| b i ∈ F p }
peut s’´ ecrire comme
F p r \ {0} = {x
i
| i = 0, . . . , p
r
− 2}
o` u les puissances x
i de x sont prises modulo Q(x).
Exemple 8.8 Prenons p = 2. On va montrer que le polynˆ ome Q(x) = x
3 + x + 1 est
irr´ eductible sur F 2 . En effet, supposons que Q(x) = Q 1 (x)Q 2 (x). Puisque Q(x) est de
degr´ e 3, soit Q 1 (x) soit Q 2 (x) est de degr´ e 1 et appartient ` a l’ensemble {x, x + 1}. Si x
divise Q(x), alors on devrait avoir Q(0) = 0, ce qui n’est pas vrai. Si x + 1 divise Q(x),
alors on devrait avoir Q(1) = 0, ce qui n’est pas vrai non plus. Donc, ni x ni x + 1 ne
divise Q(x). Par cons´ equent, Q(x) est irr´ eductible. Les ´ el´ ements non nuls de F 2 3 sont
donn´ es par {1, x, x + 1, x
2 , x
2 + 1, x
2 + x, x
2 + x + 1}. V´ erifions que ce sont tous des
puissances de x. En effet, Q(x) = 0 donne x
3 = x + 1, donc
x
4 = x(x + 1) = x
2 + x,
x
5 = x(x
2 + x) = x
3 + x
2 = (x + 1) + x
2 = x
2 + x + 1,
x
6 = x(x
2 + x + 1) = x
3 + x
2 + x = (x + 1) + x
2 + x = x
2 + 1,
x
7 = x(x
2 + 1) = x
3 + x = (x + 1) + x = 1.
Th´ eor` eme 8.9 Si les coefficients q 0 , . . . , q r−1 d’un registre `
a d´ ecalage sont choisis tels
que le polynˆ ome
Q(x) = x
r + q r−1 x
r−1 + · · · + q 1 x + q 0
(8.5)
est primitif sur F 2 , alors, pour toute suite (a 0 , . . . , a r−1 ) de conditions initiales, telle
que les a i ne sont pas tous nuls, la suite g´ en´ er´ ee par le registre est p´ eriodique de p´ eriode
2
r
− 1.