258
8 G´ en´ erateurs de nombres al´ eatoires
Ainsi T (bx) = b r−2 + q r−1 b r−1 = a 1 . Comme b r−1 est d´ ej` a connu, cela nous permet de
trouver b r−2 .
On trouve ainsi tous les b i . En effet, supposons que b i+1 , . . . , b r−1 aient d´ ej` a ´ et´ e
trouv´ es. Consid´ erons bx
r−1−i . Alors,
bx
r−1−i = (b 0 + b 1 x + · · · + b r−1 x
r−1 )x
r−1−i
= b 0 x
r−1−i + b 1 x
r−i + · · · + b i x
r−1 + x
r P (x, b i+1 , . . . , b r−1 ),
o` u P (x, b i+1 , . . . , b r−1 ) est un polynˆ ome en x dont les coefficients d´ ependent seulement
de b i+1 , . . . , b r−1 , c’est-` a-dire des coefficients d´ ej` a connus. Alors,
T (bx
r−1−i ) = b i + R(b i+1 , . . . b r−1 ).
La formule de R(b i+1 , . . . b r−1 ) n’est pas simple, mais ce qui est important, c’est que cette
expression ne d´ epend que des b i+1 , . . . , b r−1 d´ ej` a connus. Alors, on peut trouver le b i de
l’´ equation T (bx
r−1−i ) = a r−1−i , et ce processus d´ etermine uniquement le polynˆ ome b.
D´ efinition 8.11 On consid` ere un registre `
a d´ ecalage de r cases dont les coefficients
q 0 , . . . , q r−1 et les conditions initiales sont choisis de telle sorte que la suite g´ en´ er´ ee soit
p´ eriodique de p´ eriode 2
r
− 1. Alors, on apelle fenˆ etre une sous-suite de longueur 2
r
− 1
qui est r´ ep´ et´ ee p´ eriodiquement.
Corollaire 8.12 Consid´ erons un registre `
a d´ ecalage de r cases dont les coefficients
q 0 , . . . , q r−1 sont choisis tels que le polynˆ ome Q(x) de (8.5) est primitif sur F 2 . Alors,
´ etant donn´ e des conditions initiales (a 0 , . . . , a r−1 ) telles que les a i ne sont pas tous nuls,
toutes les sous-suites de longueur r apparaissent exactement une fois dans la fenˆ etre de
longueur 2
r
− 1, sauf la sous-suite nulle. (Dans ce contexte, on regarde la fenˆ etre comme
une suite cyclique, en identifiant l’indice n + 2
r
− 1 ` a l’indice n : ceci veut dire qu’on
permet aussi des sous-suites ` a cheval sur deux p´ eriodes.)
Preuve ´
Etant donn´ e une fenˆ etre a 0 , . . . a 2 r −2 de longueur 2
r
− 1 repr´ esentant une
p´ eriode de la suite, il existe 2
r
− 1 sous-suites de longueur r commen¸ cant chacune en
un a i distinct. (Si i ≥ 2
r
− r, alors en utilisant la p´ eriodicit´ e, la sous-suite de la suite
initiale commen¸ cant en a i co¨ ıncide avec a i , . . . , a 2 r −2 , a 0 , . . . , a i−2 r +r .) On a exactement
2
r suites distinctes de longueur r, car on a deux choix pour chaque entr´ ee. Parmi cellesci, on en a exactement 2
r
− 1 dont au moins un ´ el´ ement est non nul. Donc, chaque
sous-suite de longueur r apparaˆ ıtra au moins une fois si elle apparaˆ ıt au plus une fois.
Supposons qu’une sous-suite de longueur r apparaisse deux fois et commence en a i et
en a j , 0 < j − i < 2
r
− 1. Alors, comme l’´ etat du registre est le mˆ eme en a i et en a j ,
on aura, pour tout n ≥ j, a n = a n−j+i , ce qui contredit le fait que la p´ eriode minimale
de la suite {a n } est 2
r
− 1. Donc, chaque sous-suite non nulle de longueur r apparaˆ ıt
exactement une fois dans une fenˆ etre de longueur 2
r
− 1.
8 G´ en´ erateurs de nombres al´ eatoires
Ainsi T (bx) = b r−2 + q r−1 b r−1 = a 1 . Comme b r−1 est d´ ej` a connu, cela nous permet de
trouver b r−2 .
On trouve ainsi tous les b i . En effet, supposons que b i+1 , . . . , b r−1 aient d´ ej` a ´ et´ e
trouv´ es. Consid´ erons bx
r−1−i . Alors,
bx
r−1−i = (b 0 + b 1 x + · · · + b r−1 x
r−1 )x
r−1−i
= b 0 x
r−1−i + b 1 x
r−i + · · · + b i x
r−1 + x
r P (x, b i+1 , . . . , b r−1 ),
o` u P (x, b i+1 , . . . , b r−1 ) est un polynˆ ome en x dont les coefficients d´ ependent seulement
de b i+1 , . . . , b r−1 , c’est-` a-dire des coefficients d´ ej` a connus. Alors,
T (bx
r−1−i ) = b i + R(b i+1 , . . . b r−1 ).
La formule de R(b i+1 , . . . b r−1 ) n’est pas simple, mais ce qui est important, c’est que cette
expression ne d´ epend que des b i+1 , . . . , b r−1 d´ ej` a connus. Alors, on peut trouver le b i de
l’´ equation T (bx
r−1−i ) = a r−1−i , et ce processus d´ etermine uniquement le polynˆ ome b.
D´ efinition 8.11 On consid` ere un registre `
a d´ ecalage de r cases dont les coefficients
q 0 , . . . , q r−1 et les conditions initiales sont choisis de telle sorte que la suite g´ en´ er´ ee soit
p´ eriodique de p´ eriode 2
r
− 1. Alors, on apelle fenˆ etre une sous-suite de longueur 2
r
− 1
qui est r´ ep´ et´ ee p´ eriodiquement.
Corollaire 8.12 Consid´ erons un registre `
a d´ ecalage de r cases dont les coefficients
q 0 , . . . , q r−1 sont choisis tels que le polynˆ ome Q(x) de (8.5) est primitif sur F 2 . Alors,
´ etant donn´ e des conditions initiales (a 0 , . . . , a r−1 ) telles que les a i ne sont pas tous nuls,
toutes les sous-suites de longueur r apparaissent exactement une fois dans la fenˆ etre de
longueur 2
r
− 1, sauf la sous-suite nulle. (Dans ce contexte, on regarde la fenˆ etre comme
une suite cyclique, en identifiant l’indice n + 2
r
− 1 ` a l’indice n : ceci veut dire qu’on
permet aussi des sous-suites ` a cheval sur deux p´ eriodes.)
Preuve ´
Etant donn´ e une fenˆ etre a 0 , . . . a 2 r −2 de longueur 2
r
− 1 repr´ esentant une
p´ eriode de la suite, il existe 2
r
− 1 sous-suites de longueur r commen¸ cant chacune en
un a i distinct. (Si i ≥ 2
r
− r, alors en utilisant la p´ eriodicit´ e, la sous-suite de la suite
initiale commen¸ cant en a i co¨ ıncide avec a i , . . . , a 2 r −2 , a 0 , . . . , a i−2 r +r .) On a exactement
2
r suites distinctes de longueur r, car on a deux choix pour chaque entr´ ee. Parmi cellesci, on en a exactement 2
r
− 1 dont au moins un ´ el´ ement est non nul. Donc, chaque
sous-suite de longueur r apparaˆ ıtra au moins une fois si elle apparaˆ ıt au plus une fois.
Supposons qu’une sous-suite de longueur r apparaisse deux fois et commence en a i et
en a j , 0 < j − i < 2
r
− 1. Alors, comme l’´ etat du registre est le mˆ eme en a i et en a j ,
on aura, pour tout n ≥ j, a n = a n−j+i , ce qui contredit le fait que la p´ eriode minimale
de la suite {a n } est 2
r
− 1. Donc, chaque sous-suite non nulle de longueur r apparaˆ ıt
exactement une fois dans une fenˆ etre de longueur 2
r
− 1.