254
8 G´ en´ erateurs de nombres al´ eatoires
o` u toutes les op´ erations sont effectu´ ees modulo 2. Alors, le vecteur repr´ esentant les
symboles des cases ` a l’instant j + 1 est donn´ e par
x j+1 = Ax j .
(8.4)
(Exercice : v´ erifier !)
Avant de passer `
a des g´ en´ eralisations, voyons d´ ej` a un avantage de cette nouvelle
pr´ esentation. Supposons que l’on veuille passer directement de x j ` a x j+k sans calculer
les ´ etapes interm´ ediaires. On a x j+k = A
k x j . Donc, si on calcule la matrice A
k , on peut
automatiser le calcul de x j+k en fonction de x j . Le fait de pouvoir automatiser avec des
calculs raisonnables le passage de x j ` a x j+k est une propri´ et´ e recherch´ ee dans les bons
g´ en´ erateurs de nombres al´ eatoires.
Comment calculer A
k si k est grand ? En g´ en´ eral, si on prend une matrice A ` a
coefficients r´ eels, les coefficients de A
k peuvent devenir tr` es grands en valeur absolue.
Ici, toutes les entr´ ees de A sont des ´ el´ ements de {0, 1}, et les op´ erations sont l’addition
et la multiplication modulo 2. Donc, les entr´ ees de A
k sont aussi des ´ el´ ements de {0, 1}.
Mais si k est grand, il faut user d’astuce pour faire les calculs en temps raisonnable.
D´ ecomposons k en base 2 :
k = b 0 + b 1 2 + b 2 2
2 + · · · + b s 2
s .
Alors, on pose A 0 = A et on calcule
A 1 = A
2 ,
A 2 = A
4 = A
2
1 ,
. . .
A s = A
2
s = A
2
s−1 ,
et finalement
A
k =
{i|bi=1}
A i .
Remarquons que chacune des A i est le produit de deux matrices. Il faudra donc faire
s produits matriciels pour calculer toutes les matrices A i . Finalement,
{i|bi=1} A i
contient au plus s + 1 facteurs. Ainsi, A
k peut ˆ etre calcul´ e en au plus 2s ≤ 2 log 2 k
produits matriciels.
On voit aussi qu’on peut obtenir d’autres g´ en´ erateurs de nombres al´ eatoires en gardant l’´ etape de r´ ecurrence (8.4) et en permettant d’autres formes de matrice A.
8.3 Le contexte g´ en´ eral des g´ en´ erateurs F p -lin´ eaires
8.3.1 Le cas p = 2
Commen¸ cons par le cas p = 2. Le corps F 2 est l’ensemble {0, 1} muni des op´ erations
d’addition et de multiplication modulo 2.
8 G´ en´ erateurs de nombres al´ eatoires
o` u toutes les op´ erations sont effectu´ ees modulo 2. Alors, le vecteur repr´ esentant les
symboles des cases ` a l’instant j + 1 est donn´ e par
x j+1 = Ax j .
(8.4)
(Exercice : v´ erifier !)
Avant de passer `
a des g´ en´ eralisations, voyons d´ ej` a un avantage de cette nouvelle
pr´ esentation. Supposons que l’on veuille passer directement de x j ` a x j+k sans calculer
les ´ etapes interm´ ediaires. On a x j+k = A
k x j . Donc, si on calcule la matrice A
k , on peut
automatiser le calcul de x j+k en fonction de x j . Le fait de pouvoir automatiser avec des
calculs raisonnables le passage de x j ` a x j+k est une propri´ et´ e recherch´ ee dans les bons
g´ en´ erateurs de nombres al´ eatoires.
Comment calculer A
k si k est grand ? En g´ en´ eral, si on prend une matrice A ` a
coefficients r´ eels, les coefficients de A
k peuvent devenir tr` es grands en valeur absolue.
Ici, toutes les entr´ ees de A sont des ´ el´ ements de {0, 1}, et les op´ erations sont l’addition
et la multiplication modulo 2. Donc, les entr´ ees de A
k sont aussi des ´ el´ ements de {0, 1}.
Mais si k est grand, il faut user d’astuce pour faire les calculs en temps raisonnable.
D´ ecomposons k en base 2 :
k = b 0 + b 1 2 + b 2 2
2 + · · · + b s 2
s .
Alors, on pose A 0 = A et on calcule
A 1 = A
2 ,
A 2 = A
4 = A
2
1 ,
. . .
A s = A
2
s = A
2
s−1 ,
et finalement
A
k =
{i|bi=1}
A i .
Remarquons que chacune des A i est le produit de deux matrices. Il faudra donc faire
s produits matriciels pour calculer toutes les matrices A i . Finalement,
{i|bi=1} A i
contient au plus s + 1 facteurs. Ainsi, A
k peut ˆ etre calcul´ e en au plus 2s ≤ 2 log 2 k
produits matriciels.
On voit aussi qu’on peut obtenir d’autres g´ en´ erateurs de nombres al´ eatoires en gardant l’´ etape de r´ ecurrence (8.4) et en permettant d’autres formes de matrice A.
8.3 Le contexte g´ en´ eral des g´ en´ erateurs F p -lin´ eaires
8.3.1 Le cas p = 2
Commen¸ cons par le cas p = 2. Le corps F 2 est l’ensemble {0, 1} muni des op´ erations
d’addition et de multiplication modulo 2.