1.4 Les registres ` a d´ ecalage
25
1.4.2 Preuve du th´ eor` eme 1.4
Nous choisissons un polynˆ ome P (x) primitif de degr´ e r sur F 2
P (x) = x
r + q r−1 x
r−1 + · · · + q 1 x + q 0
qui nous permet de construire le corps F 2 r .
Les q i du registre `
a d´ ecalage sont les coefficients du polynˆ ome P (x). Pour construire
de bonnes conditions initiales, on prend un r-tuple b = (b 0 , . . . , b r−1 ) ∈ F
r
2 \ {0} que l’on
identifie au polynˆ ome b r−1 x
r−1 + · · · + b 1 x + b 0 . On prend comme ´ el´ ements initiaux
a 0
= T (b)
= b r−1 ,
a 1
= T (xb),
. . .
a r−1 = T (x
r−1 b).
(1.32)
Voyons comment calculer a 1 .
a 1 = T (bx) = T (b r−1 x
r + b r−2 x
r−1 + · · · + b 0 x)
= T (b r−1 (q r−1 x
r−1 + · · · + q 1 x + q 0 ) + b r−2 x
r−1 + · · · + b 0 x)
= T ((b r−1 q r−1 + b r−2 )x
r−1 + . . . )
= b r−1 q r−1 + b r−2 .
(1.33)
Un calcul similaire permet de calculer a 2 , . . . , a r−1 . Les formules deviennent vite ´ enormes
mais le calcul se fait tr` es bien dans les exemples num´ eriques quand on remplace les q i
et les b i par des valeurs 0 ou 1.
Exemple 1.11 Dans l’exemple 1.5, le polynˆ ome consid´ er´ e est P (x) = x
4 + x + 1. On
a vu `
a l’exemple 1.8 que ce polynˆ ome est primitif. Le polynˆ ome b choisi est simplement
b = 1. Alors, on doit prendre a 0 = T (1) = 0, a 1 = T (x) = 0, a 2 = T (x
2 ) = 0 et
a 3 = T (x
3 ) = 1.
Proposition 1.12 Choisissons pour les q i d’un registre `
a d´ ecalage les coefficients d’un
polynˆ ome primitif de degr´ e r sur F 2
P (x) = x
r + q r−1 x
r−1 + · · · + q 1 x + q 0 .
Soit b = b r−1 x
r−1 + · · · + b 1 x + b 0 . On prend comme ´ el´ ements initiaux (a 0 , . . . , a r−1 )
donn´ es en (1.32). Alors, la suite g´ en´ er´ ee par le registre `
a d´ ecalage est la suite {a n },
avec a n = T (x
n b). Elle est p´ eriodique, et sa p´ eriode divise 2
r
− 1.
Preuve On utilise que P (x) = 0, c’est-` a-dire le fait que x
r = q r−1 x
r−1 + · · ·+ q 1 x+ q 0 .
Alors,
25
1.4.2 Preuve du th´ eor` eme 1.4
Nous choisissons un polynˆ ome P (x) primitif de degr´ e r sur F 2
P (x) = x
r + q r−1 x
r−1 + · · · + q 1 x + q 0
qui nous permet de construire le corps F 2 r .
Les q i du registre `
a d´ ecalage sont les coefficients du polynˆ ome P (x). Pour construire
de bonnes conditions initiales, on prend un r-tuple b = (b 0 , . . . , b r−1 ) ∈ F
r
2 \ {0} que l’on
identifie au polynˆ ome b r−1 x
r−1 + · · · + b 1 x + b 0 . On prend comme ´ el´ ements initiaux
a 0
= T (b)
= b r−1 ,
a 1
= T (xb),
. . .
a r−1 = T (x
r−1 b).
(1.32)
Voyons comment calculer a 1 .
a 1 = T (bx) = T (b r−1 x
r + b r−2 x
r−1 + · · · + b 0 x)
= T (b r−1 (q r−1 x
r−1 + · · · + q 1 x + q 0 ) + b r−2 x
r−1 + · · · + b 0 x)
= T ((b r−1 q r−1 + b r−2 )x
r−1 + . . . )
= b r−1 q r−1 + b r−2 .
(1.33)
Un calcul similaire permet de calculer a 2 , . . . , a r−1 . Les formules deviennent vite ´ enormes
mais le calcul se fait tr` es bien dans les exemples num´ eriques quand on remplace les q i
et les b i par des valeurs 0 ou 1.
Exemple 1.11 Dans l’exemple 1.5, le polynˆ ome consid´ er´ e est P (x) = x
4 + x + 1. On
a vu `
a l’exemple 1.8 que ce polynˆ ome est primitif. Le polynˆ ome b choisi est simplement
b = 1. Alors, on doit prendre a 0 = T (1) = 0, a 1 = T (x) = 0, a 2 = T (x
2 ) = 0 et
a 3 = T (x
3 ) = 1.
Proposition 1.12 Choisissons pour les q i d’un registre `
a d´ ecalage les coefficients d’un
polynˆ ome primitif de degr´ e r sur F 2
P (x) = x
r + q r−1 x
r−1 + · · · + q 1 x + q 0 .
Soit b = b r−1 x
r−1 + · · · + b 1 x + b 0 . On prend comme ´ el´ ements initiaux (a 0 , . . . , a r−1 )
donn´ es en (1.32). Alors, la suite g´ en´ er´ ee par le registre `
a d´ ecalage est la suite {a n },
avec a n = T (x
n b). Elle est p´ eriodique, et sa p´ eriode divise 2
r
− 1.
Preuve On utilise que P (x) = 0, c’est-` a-dire le fait que x
r = q r−1 x
r−1 + · · ·+ q 1 x+ q 0 .
Alors,