266
8 G´ en´ erateurs de nombres al´ eatoires
6. Montrer que le polynˆ ome x
4 + x
3 + x
2 + x+1 est irr´ eductible, mais n’est pas primitif
sur F 2 . V´ erifier d’autre part que, si on prend (q 0 , q 1 , q 2 , q 3 ) = (1, 1, 1, 1) comme
coefficients d’un registre ` a d´ ecalage, alors aucune suite g´ en´ er´ ee par le registre ` a
d´ ecalage n’est de p´ eriode 15.
7. On consid` ere le registre ` a d´ ecalage de coefficients (q 0 , q 1 , q 2 , q 3 , q 4 ) = (1, 0, 1, 0, 0) et
conditions initiales (a 0 , a 1 , a 2 , a 3 , a 4 ) = (0, 0, 0, 0, 1).
a) V´ erifier que la suite g´ en´ er´ ee est p´ eriodique de p´ eriode 31 en ´ enum´ erant explicitement a i , i = 0, . . . , 35 (s’assurer que a 0 = a 31 , a 1 = a 32 , a 2 = a 33 , a 3 = a 34 ,
a 4 = a 35 ).
b) V´ erifier que 1 apparaˆ ıt 16 fois sur 31.
c) V´ erifier que chaque sous-suite de longueur 2 apparaˆ ıt huit fois sur 31, sauf 00
qui apparaˆ ıt sept fois sur 31.
d) V´ erifier que chaque sous-suite de longueur 3 apparaˆ ıt quatre fois sur 31, sauf
000 qui apparaˆ ıt trois fois sur 31.
e) V´ erifier que chaque sous-suite de longueur quatre apparaˆ ıt deux fois sur 31,
sauf 0000 qui apparaˆ ıt une fois sur 31.
f) V´ erifier que chaque sous-suite de longueur 5 apparaˆ ıt une fois sur 31, sauf
00000. En d´ eduire qu’on aurait pu prendre n’importe quelle sous-suite non nulle de
longueur 5 comme ensemble de conditions initiales.
g) En d´ eduire que, si on consid` ere des sous-suites de longueur k ≤ r et si on
´ elimine les suites qui ne contiennent que des z´ eros, on obtient un g´ en´ erateur dont
toutes les sorties sont ´ equiprobables.
8. Le registre de l’exercice 7 g´ en` ere une suite {a n }.
a) Donner la fonction qui `
a a n associe a n+2 . (Suggestion : utiliser la forme matricielle.)
b) Donner la fonction qui `
a a n associe a n+10 .
9. Trouver tous les polynˆ omes irr´ eductibles de degr´ e 2 sur F 3 . Lesquels sont primitifs ?
10. Le but de l’exercice est de montrer que le polynˆ ome Q(x) = x
4
− x − 1 est primitif
sur F 3 .
a) Montrer que Q(x) est irr´ eductible sur F 3 . Pour cela, vous aurez besoin de
l’exercice 9.
b) Montrer que Q(x) est primitif, c’est-` a-dire que x
k
= 1 si k < 80. Pour cela, il
faut calculer les puissances x
k en utilisant la r` egle x
4 = x + 1. Par exemple,
⎧
⎪ ⎨
⎪ ⎩
x
5 = x(x + 1) = x
2 + x,
x
6 = x(x
2 + x) = x
3 + x
2 ,
x
7 = x(x
3 + x
2 ) = x
4 + x
3 = (x + 1) + x
3 = x
3 + x + 1.
(Le calcul peut sembler fastidieux. On peut le simplifier en utilisant le fait que
x
80 = 1 et le lemme 8.2 qui garantit que si x
k = 1, k < 80, alors k | 80. Ceci
permet de se limiter `
a calculer x
k pour k, un diviseur de 80.)
8 G´ en´ erateurs de nombres al´ eatoires
6. Montrer que le polynˆ ome x
4 + x
3 + x
2 + x+1 est irr´ eductible, mais n’est pas primitif
sur F 2 . V´ erifier d’autre part que, si on prend (q 0 , q 1 , q 2 , q 3 ) = (1, 1, 1, 1) comme
coefficients d’un registre ` a d´ ecalage, alors aucune suite g´ en´ er´ ee par le registre ` a
d´ ecalage n’est de p´ eriode 15.
7. On consid` ere le registre ` a d´ ecalage de coefficients (q 0 , q 1 , q 2 , q 3 , q 4 ) = (1, 0, 1, 0, 0) et
conditions initiales (a 0 , a 1 , a 2 , a 3 , a 4 ) = (0, 0, 0, 0, 1).
a) V´ erifier que la suite g´ en´ er´ ee est p´ eriodique de p´ eriode 31 en ´ enum´ erant explicitement a i , i = 0, . . . , 35 (s’assurer que a 0 = a 31 , a 1 = a 32 , a 2 = a 33 , a 3 = a 34 ,
a 4 = a 35 ).
b) V´ erifier que 1 apparaˆ ıt 16 fois sur 31.
c) V´ erifier que chaque sous-suite de longueur 2 apparaˆ ıt huit fois sur 31, sauf 00
qui apparaˆ ıt sept fois sur 31.
d) V´ erifier que chaque sous-suite de longueur 3 apparaˆ ıt quatre fois sur 31, sauf
000 qui apparaˆ ıt trois fois sur 31.
e) V´ erifier que chaque sous-suite de longueur quatre apparaˆ ıt deux fois sur 31,
sauf 0000 qui apparaˆ ıt une fois sur 31.
f) V´ erifier que chaque sous-suite de longueur 5 apparaˆ ıt une fois sur 31, sauf
00000. En d´ eduire qu’on aurait pu prendre n’importe quelle sous-suite non nulle de
longueur 5 comme ensemble de conditions initiales.
g) En d´ eduire que, si on consid` ere des sous-suites de longueur k ≤ r et si on
´ elimine les suites qui ne contiennent que des z´ eros, on obtient un g´ en´ erateur dont
toutes les sorties sont ´ equiprobables.
8. Le registre de l’exercice 7 g´ en` ere une suite {a n }.
a) Donner la fonction qui `
a a n associe a n+2 . (Suggestion : utiliser la forme matricielle.)
b) Donner la fonction qui `
a a n associe a n+10 .
9. Trouver tous les polynˆ omes irr´ eductibles de degr´ e 2 sur F 3 . Lesquels sont primitifs ?
10. Le but de l’exercice est de montrer que le polynˆ ome Q(x) = x
4
− x − 1 est primitif
sur F 3 .
a) Montrer que Q(x) est irr´ eductible sur F 3 . Pour cela, vous aurez besoin de
l’exercice 9.
b) Montrer que Q(x) est primitif, c’est-` a-dire que x
k
= 1 si k < 80. Pour cela, il
faut calculer les puissances x
k en utilisant la r` egle x
4 = x + 1. Par exemple,
⎧
⎪ ⎨
⎪ ⎩
x
5 = x(x + 1) = x
2 + x,
x
6 = x(x
2 + x) = x
3 + x
2 ,
x
7 = x(x
3 + x
2 ) = x
4 + x
3 = (x + 1) + x
3 = x
3 + x + 1.
(Le calcul peut sembler fastidieux. On peut le simplifier en utilisant le fait que
x
80 = 1 et le lemme 8.2 qui garantit que si x
k = 1, k < 80, alors k | 80. Ceci
permet de se limiter `
a calculer x
k pour k, un diviseur de 80.)