8.4 G´ en´ erateur r´ ecursif multiple combin´ e
261
est primitif sur F p , alors le g´ en´ erateur F p -lin´ eaire donn´ e en (8.6) g´ en` ere une suite de
p´ eriode p
r
− 1.
Si on prend une suite (a 0 , . . . , a r−1 ) de conditions initiales, telle que les a i ne sont
pas tous nuls, alors, dans une fenˆ etre de longueur p
r
− 1 de la suite g´ en´ er´ ee par le
registre, toute sous-suite de longueur k avec k ≤ r apparaˆ ıt p
r−k fois, sauf la sous-suite
nulle qui apparaˆ ıt p
r−k
− 1 fois. (On consid` ere la fenˆ etre comme une suite cyclique, en
identifiant l’indice n + p
r
− 1 ` a l’indice n.)
Preuve Comme la preuve est identique ` a celle des th´ eor` emes 8.9 et 8.13, nous la
laissons en exercice.
En pratique, on travaille souvent avec des g´ en´ erateurs F p -lin´ eaires dans lesquels le
polynˆ ome Q(x) n’a que deux coefficients q i non nuls, soit q 0 et q s , 0 < s ≤ r − 1. Ceci
rend les calculs tr` es simples.
Exemple 8.16 On consid` ere p = 3 et le polynˆ ome Q(x) = x
4
− x − 1. Nous allons
admettre que ce polynˆ ome est primitif et laisser les d´ etails pour l’exercice 10. Si l’on
prend les conditions initiales (a 0 , a 1 , a 2 , a 3 ) = (0, 0, 0, 1), alors la suite {a n } engendr´ ee
par le g´ en´ erateur F 3 -lin´ eaire associ´ e est de p´ eriode 3
4
− 1 = 80, et la fenˆ etre de longueur
80 qui est r´ ep´ et´ ee est :
0 0 0 1 0 0 1 1 0 1 2 1 1 0 0 2 1 0 2 0 1 2 2 1 0 1 0 1 1 1 1 2 2 2 0 1 1 2 1 2
0 0 0 2 0 0 2 2 0 2 1 2 2 0 0 1 2 0 1 0 2 1 1 2 0 2 0 2 2 2 2 1 1 1 0 2 2 1 2 1.
(8.8)
On peut v´ erifier les bonnes propri´ et´ es statistiques de cette suite. En effet, 1 et 2 apparaissent chacun 27 fois, alors que 0 apparaˆ ıt 26 fois. Toutes les sous-suites de longueur
2 apparaissent chacune neuf fois, sauf 00 qui apparaˆ ıt huit fois. Toutes les sous-suites
de longueur 3 apparaissent chacune trois fois sauf 000 qui apparaˆ ıt deux fois. Toutes les
sous-suites de longueur 4 apparaissent chacune une fois, sauf 0000.
8.4 G´ en´ erateur r´ ecursif multiple combin´ e
Les g´ en´ erateurs F p -lin´ eaires qui n’ont que deux coefficients non nuls, q 0 et q s , 0 <
s ≤ r − 1, conduisent `
a des calculs tr` es simples. Par contre, ils ne se comportent pas tr` es
bien statistiquement. Pour pallier cet inconv´ enient, on combine plusieurs g´ en´ erateurs de
ce type caract´ eris´ es par des entiers premiers p distincts et des polynˆ omes Q(x) distincts,
mais de mˆ eme degr´ e.
D´ efinition 8.17 On consid` ere m r´ ecurrences lin´ eaires
a n,j = q 0,j a n−r,j + q 1,j a n−r+1,j + · · · + q r−1,j a n−1,j (mod p j ),
j = 1, . . . m, satisfaisant aux hypoth` eses du th´ eor` eme 8.15, o` u les p j sont des entiers
premiers distincts. La fonction « sortie » transforme les vecteurs (a n,1 , . . . , a n,m ) en
nombres r´ eels de [0, 1] par la formule
261
est primitif sur F p , alors le g´ en´ erateur F p -lin´ eaire donn´ e en (8.6) g´ en` ere une suite de
p´ eriode p
r
− 1.
Si on prend une suite (a 0 , . . . , a r−1 ) de conditions initiales, telle que les a i ne sont
pas tous nuls, alors, dans une fenˆ etre de longueur p
r
− 1 de la suite g´ en´ er´ ee par le
registre, toute sous-suite de longueur k avec k ≤ r apparaˆ ıt p
r−k fois, sauf la sous-suite
nulle qui apparaˆ ıt p
r−k
− 1 fois. (On consid` ere la fenˆ etre comme une suite cyclique, en
identifiant l’indice n + p
r
− 1 ` a l’indice n.)
Preuve Comme la preuve est identique ` a celle des th´ eor` emes 8.9 et 8.13, nous la
laissons en exercice.
En pratique, on travaille souvent avec des g´ en´ erateurs F p -lin´ eaires dans lesquels le
polynˆ ome Q(x) n’a que deux coefficients q i non nuls, soit q 0 et q s , 0 < s ≤ r − 1. Ceci
rend les calculs tr` es simples.
Exemple 8.16 On consid` ere p = 3 et le polynˆ ome Q(x) = x
4
− x − 1. Nous allons
admettre que ce polynˆ ome est primitif et laisser les d´ etails pour l’exercice 10. Si l’on
prend les conditions initiales (a 0 , a 1 , a 2 , a 3 ) = (0, 0, 0, 1), alors la suite {a n } engendr´ ee
par le g´ en´ erateur F 3 -lin´ eaire associ´ e est de p´ eriode 3
4
− 1 = 80, et la fenˆ etre de longueur
80 qui est r´ ep´ et´ ee est :
0 0 0 1 0 0 1 1 0 1 2 1 1 0 0 2 1 0 2 0 1 2 2 1 0 1 0 1 1 1 1 2 2 2 0 1 1 2 1 2
0 0 0 2 0 0 2 2 0 2 1 2 2 0 0 1 2 0 1 0 2 1 1 2 0 2 0 2 2 2 2 1 1 1 0 2 2 1 2 1.
(8.8)
On peut v´ erifier les bonnes propri´ et´ es statistiques de cette suite. En effet, 1 et 2 apparaissent chacun 27 fois, alors que 0 apparaˆ ıt 26 fois. Toutes les sous-suites de longueur
2 apparaissent chacune neuf fois, sauf 00 qui apparaˆ ıt huit fois. Toutes les sous-suites
de longueur 3 apparaissent chacune trois fois sauf 000 qui apparaˆ ıt deux fois. Toutes les
sous-suites de longueur 4 apparaissent chacune une fois, sauf 0000.
8.4 G´ en´ erateur r´ ecursif multiple combin´ e
Les g´ en´ erateurs F p -lin´ eaires qui n’ont que deux coefficients non nuls, q 0 et q s , 0 <
s ≤ r − 1, conduisent `
a des calculs tr` es simples. Par contre, ils ne se comportent pas tr` es
bien statistiquement. Pour pallier cet inconv´ enient, on combine plusieurs g´ en´ erateurs de
ce type caract´ eris´ es par des entiers premiers p distincts et des polynˆ omes Q(x) distincts,
mais de mˆ eme degr´ e.
D´ efinition 8.17 On consid` ere m r´ ecurrences lin´ eaires
a n,j = q 0,j a n−r,j + q 1,j a n−r+1,j + · · · + q r−1,j a n−1,j (mod p j ),
j = 1, . . . m, satisfaisant aux hypoth` eses du th´ eor` eme 8.15, o` u les p j sont des entiers
premiers distincts. La fonction « sortie » transforme les vecteurs (a n,1 , . . . , a n,m ) en
nombres r´ eels de [0, 1] par la formule