Travaux pratiques
est la décomposition de f en facteurs irréductibles (unitaires) dans F p [x], alors
h i =
e j =i f j , d’où l’existence et l’unicité de la factorisation sans facteur carré.
Expliquons comment l’obtenir (sans factoriser !). Quitte à diviser par λ, on
suppose f unitaire. Partant de f =
i ih
i h
i−1
i
j =i h
j
j , le lecteur vérifiera que
u = pgcd(f, f
) =
pi
h
i−1
i
p|i
h
i
i .
On définit alors deux suites u k et v k par récurrence comme suit : u 1 = u et
v 1 = f /u =
pi h i . Pour k 1, on pose v k+1 = pgcd(u k , v k ) si p k et v k+1 = v k
si p | k, puis u k+1 = u k /v k+1 . On vérifie facilement par récurrence que
u k =
i>k,pi
h
i−k
i
p|i
h
i
i et v k =
ik,pi
h i .
Il en résulte que h k = v k /v k+1 si p k. On obtient ainsi des h k jusqu’à ce que v k
soit un polynôme constant, auquel cas u k−1 =
p|i h i
i = g p . On remplace alors f
par g et l’on recommence.
2. Écrire une procédure sans2fact:=proc(f,p) renvoyant la factorisation sans
facteur carré de f , formatée comme une liste [λ, [h 1 , e 1 ], . . . , [h s , e s ]]. Tester
avec f (x) = x 15 + 2x 14 + 2x 12 + x 11 + 2x 10 + 2x 8 + x 7 + 2x 6 + 2x 4 et p = 3 ;
comparer avec le résultat de la commande Maple Sqrfree(f) mod 3.
La deuxième étape consiste à factoriser P = h (sans facteur carré) en un produit d’irréductibles distincts : P =
r
i=1 P i . D’après le théorème chinois, l’algèbre
A = F p [X]/(P ) est isomorphe au produit
r
i=1 F p [x]/(P i ). Comme les P i sont
irréductibles, chaque F p [X]/(P i ) est un corps (à p deg(P i ) éléments). Le Frobenius
ϕ p : A → A, donné par a → a p , est un morphisme d’algèbres. Sa matrice, dans la
base 1, x, . . . , x n−1 , où n = deg P , s’appelle la matrice de Berlekamp.
☞ Quelques remarques concernant l’algèbre linéaire sur F p en Maple : on
utilise la librairie dédiée : faire with(LinearAlgebra:-Modular). La matrice identité I n de M n (F p ) se définit alors par la commande
Create(p,n,n,identity,integer).
Déclarant une variable M:=Mod(p,Matrix(n,n),integer), on remplit ensuite
la matrice M par des affectations M[i,j]:=... Le noyau de M s’obtient via
Nullspace(M) mod p ; l’algorithme sous-jacent est l’algorithme de Gauss-Jordan
(appliqué à la transposée de M , cf. TP.VI.A).
3. Écrire une procédure Bmatrice:=proc(P,p) renvoyant la matrice de
Berlekamp B. Tester avec P = x 4 + 1 et p = 3, par exemple, et calculer
253
est la décomposition de f en facteurs irréductibles (unitaires) dans F p [x], alors
h i =
e j =i f j , d’où l’existence et l’unicité de la factorisation sans facteur carré.
Expliquons comment l’obtenir (sans factoriser !). Quitte à diviser par λ, on
suppose f unitaire. Partant de f =
i ih
i h
i−1
i
j =i h
j
j , le lecteur vérifiera que
u = pgcd(f, f
) =
pi
h
i−1
i
p|i
h
i
i .
On définit alors deux suites u k et v k par récurrence comme suit : u 1 = u et
v 1 = f /u =
pi h i . Pour k 1, on pose v k+1 = pgcd(u k , v k ) si p k et v k+1 = v k
si p | k, puis u k+1 = u k /v k+1 . On vérifie facilement par récurrence que
u k =
i>k,pi
h
i−k
i
p|i
h
i
i et v k =
ik,pi
h i .
Il en résulte que h k = v k /v k+1 si p k. On obtient ainsi des h k jusqu’à ce que v k
soit un polynôme constant, auquel cas u k−1 =
p|i h i
i = g p . On remplace alors f
par g et l’on recommence.
2. Écrire une procédure sans2fact:=proc(f,p) renvoyant la factorisation sans
facteur carré de f , formatée comme une liste [λ, [h 1 , e 1 ], . . . , [h s , e s ]]. Tester
avec f (x) = x 15 + 2x 14 + 2x 12 + x 11 + 2x 10 + 2x 8 + x 7 + 2x 6 + 2x 4 et p = 3 ;
comparer avec le résultat de la commande Maple Sqrfree(f) mod 3.
La deuxième étape consiste à factoriser P = h (sans facteur carré) en un produit d’irréductibles distincts : P =
r
i=1 P i . D’après le théorème chinois, l’algèbre
A = F p [X]/(P ) est isomorphe au produit
r
i=1 F p [x]/(P i ). Comme les P i sont
irréductibles, chaque F p [X]/(P i ) est un corps (à p deg(P i ) éléments). Le Frobenius
ϕ p : A → A, donné par a → a p , est un morphisme d’algèbres. Sa matrice, dans la
base 1, x, . . . , x n−1 , où n = deg P , s’appelle la matrice de Berlekamp.
☞ Quelques remarques concernant l’algèbre linéaire sur F p en Maple : on
utilise la librairie dédiée : faire with(LinearAlgebra:-Modular). La matrice identité I n de M n (F p ) se définit alors par la commande
Create(p,n,n,identity,integer).
Déclarant une variable M:=Mod(p,Matrix(n,n),integer), on remplit ensuite
la matrice M par des affectations M[i,j]:=... Le noyau de M s’obtient via
Nullspace(M) mod p ; l’algorithme sous-jacent est l’algorithme de Gauss-Jordan
(appliqué à la transposée de M , cf. TP.VI.A).
3. Écrire une procédure Bmatrice:=proc(P,p) renvoyant la matrice de
Berlekamp B. Tester avec P = x 4 + 1 et p = 3, par exemple, et calculer
253