8.3 G´ en´ erateurs Fp-lin´ eaires
257
Preuve On a vu au chapitre 6 que l’ensemble
F 2 r = {b 0 + b 1 x + · · · + b r−1 x
r−1
| b i ∈ {0, 1}}
muni de l’addition et de la multiplication modulo Q(x) est un corps lorsque le polynˆ ome
Q(x) est irr´ eductible. On a aussi vu (section 1.4 du chapitre 1) que, pour la construction
du corps F 2 r , il est toujours possible de choisir un polynˆ ome Q(x) primitif, c’est-` a-dire
tel que l’ensemble des ´ el´ ements non nuls s’´ ecrit
{x
i
| i = 0, . . . , 2
r
− 2}
et que x
2
r −1 = 1. Introduisons la fonction (lin´ eaire) T : F 2 r → F 2 d´ efinie par
T (b 0 + b 1 x + · · · + b r−1 x
r−1 ) = b r−1 .
Nous allons montrer dans le lemme 8.10 ci-dessous que, pour toute suite non nulle
(a 0 , . . . , a r−1 ), il existe un unique b = b 0 + b 1 x + . . . b r−1 x
r−1 tel que a i = T (bx
i ),
i = 0, . . . , r − 1. La proposition 1.12 du chapitre 1 nous dit que, si a n est la suite g´ en´ er´ ee
par le registre ` a d´ ecalage avec les conditions initiales a i = T (bx
i ), alors, pour tout
n, on a a n = T (bx
n ). Puisque x
2
r −1 = 1, la suite a n est p´ eriodique et, pour tout n,
a n = a n+2 r −1 .
Mais N = 2
r
− 1 est-il la p´ eriode minimale ? Supposons qu’il existe m < 2
r
− 1 tel
que a n = a n+m pour tout n. Alors, a 0 = a m , . . . , a r−1 = a r+m−1 . D’apr` es le lemme 8.10
ci-dessous, il existe b
tel que a i+m = T (b
x
i ), i = 0, . . . , r − 1, et `
a cause de l’unicit´ e de
b
dans ce mˆ eme lemme, on a b
= b, et d’autre part, b
= bx
m (cette ´ egalit´ e est bien sˆ ur
modulo Q(x)). D’o` u b(x
m
− 1) = 0 et, comme b = 0, x
m = 1. Comme x est une racine
primitive, on a x
m
= 1 pour m < 2
r
− 1, d’o` u la contradiction.
Lemme 8.10 On consid` ere le corps
F 2 r = {b 0 + b 1 x + · · · + b r−1 x
r−1
| b i ∈ {0, 1}}
muni de l’addition et de la multiplication modulo Q(x), o` u Q(x) est le polynˆ ome
irr´ eductible donn´ e en (8.5). Alors, pour toute suite (a 0 , . . . , a r−1 ), il existe un unique
b = b 0 + b 1 x + . . . b r−1 x
r−1 tel que a i = T (bx
i ), i = 0, . . . , r − 1.
Preuve On consid` ere le syst` eme d’´ equations lin´ eaires T (bx
i ) = a i , i = 0, . . . , r − 1,
aux inconnues b 0 , . . . , b r−1 . Regardons la premi` ere ´ equation
T (b) = b r−1 = a 0 .
Elle nous permet de trouver b r−1 . Maintenant,
bx = (b 0 + b 1 x + · · · + b r−1 x
r−1 )x
= b 0 x + b 1 x
2 + · · · + b r−2 x
r−1 + b r−1 (q 0 + q 1 x + . . . q r−1 x
r−1 ).
257
Preuve On a vu au chapitre 6 que l’ensemble
F 2 r = {b 0 + b 1 x + · · · + b r−1 x
r−1
| b i ∈ {0, 1}}
muni de l’addition et de la multiplication modulo Q(x) est un corps lorsque le polynˆ ome
Q(x) est irr´ eductible. On a aussi vu (section 1.4 du chapitre 1) que, pour la construction
du corps F 2 r , il est toujours possible de choisir un polynˆ ome Q(x) primitif, c’est-` a-dire
tel que l’ensemble des ´ el´ ements non nuls s’´ ecrit
{x
i
| i = 0, . . . , 2
r
− 2}
et que x
2
r −1 = 1. Introduisons la fonction (lin´ eaire) T : F 2 r → F 2 d´ efinie par
T (b 0 + b 1 x + · · · + b r−1 x
r−1 ) = b r−1 .
Nous allons montrer dans le lemme 8.10 ci-dessous que, pour toute suite non nulle
(a 0 , . . . , a r−1 ), il existe un unique b = b 0 + b 1 x + . . . b r−1 x
r−1 tel que a i = T (bx
i ),
i = 0, . . . , r − 1. La proposition 1.12 du chapitre 1 nous dit que, si a n est la suite g´ en´ er´ ee
par le registre ` a d´ ecalage avec les conditions initiales a i = T (bx
i ), alors, pour tout
n, on a a n = T (bx
n ). Puisque x
2
r −1 = 1, la suite a n est p´ eriodique et, pour tout n,
a n = a n+2 r −1 .
Mais N = 2
r
− 1 est-il la p´ eriode minimale ? Supposons qu’il existe m < 2
r
− 1 tel
que a n = a n+m pour tout n. Alors, a 0 = a m , . . . , a r−1 = a r+m−1 . D’apr` es le lemme 8.10
ci-dessous, il existe b
tel que a i+m = T (b
x
i ), i = 0, . . . , r − 1, et `
a cause de l’unicit´ e de
b
dans ce mˆ eme lemme, on a b
= b, et d’autre part, b
= bx
m (cette ´ egalit´ e est bien sˆ ur
modulo Q(x)). D’o` u b(x
m
− 1) = 0 et, comme b = 0, x
m = 1. Comme x est une racine
primitive, on a x
m
= 1 pour m < 2
r
− 1, d’o` u la contradiction.
Lemme 8.10 On consid` ere le corps
F 2 r = {b 0 + b 1 x + · · · + b r−1 x
r−1
| b i ∈ {0, 1}}
muni de l’addition et de la multiplication modulo Q(x), o` u Q(x) est le polynˆ ome
irr´ eductible donn´ e en (8.5). Alors, pour toute suite (a 0 , . . . , a r−1 ), il existe un unique
b = b 0 + b 1 x + . . . b r−1 x
r−1 tel que a i = T (bx
i ), i = 0, . . . , r − 1.
Preuve On consid` ere le syst` eme d’´ equations lin´ eaires T (bx
i ) = a i , i = 0, . . . , r − 1,
aux inconnues b 0 , . . . , b r−1 . Regardons la premi` ere ´ equation
T (b) = b r−1 = a 0 .
Elle nous permet de trouver b r−1 . Maintenant,
bx = (b 0 + b 1 x + · · · + b r−1 x
r−1 )x
= b 0 x + b 1 x
2 + · · · + b r−2 x
r−1 + b r−1 (q 0 + q 1 x + . . . q r−1 x
r−1 ).