Algèbre T1
le noyau de B − I 4 . Comparer la dimension de ce noyau aux nombres de facteurs irréductibles dans la décomposition sur F 3 . Tester la conjecture que cela
suscite à l’aide d’une procédure test:=proc(P,p) et de polynômes tirés au hasard par randpol. Enfin, démontrer au papier-crayon, pour tout P =
r
i=1 P i ,
que la sous-algèbre de Berlekamp N de A, noyau de ϕ p − Id n , est isomorphe à
F r
p , via le morphisme a → (a mod P 1 , . . . , a mod P r ) du théorème Chinois.
4. Soit S une F p -base de N . Écrire une procédure Vect2Pol:=proc(v) convertissant un vecteur v = (y 1 , . . . , y n ) ∈ F r
p en le polynôme
n
i=1 y i x i−1 . En déduire
S sur l’exemple P = x 4 + 1 et p = 3.
On note S = {1, v 1 , . . . , v r−1 }. Si r 2, démontrer qu’il existe, pour tout
1 i, j r, i = j, un élément α ∈ F p et un indice 1 k r − 1 tels que
v k ≡ α mod P i et v k ≡ α mod P j (raisonner par l’absurde : si l’on avait
v k ≡ α k mod P i et v k ≡ α k mod P j pour tout 1 k r − 1, exhiber
une contradiction en regardant dans la base S un élément a tel que a ≡ 1
mod P i et a ≡ 0 mod P j ). En déduire que si Q est un diviseur de P non
irréductible, alors il existe un élément α ∈ F p et un indice 1 k r − 1 tels
que pgcd(v k − α, Q) soit un diviseur strict de Q.
Finalement, démontrer que l’algorithme suivant factorise P :
on pose i := 1 ; L := [P ] ;
# liste de polynômes dont le produit
est P
tant que longueur(L) < r
on prend Q := L[i] ;
pour tout k r − 1, α ∈ F p
on pose D := pgcd(v k − α, Q) ;
si 0 < degré(D) < degré(Q),
remplacer Q par D dans L et rajouter Q/D à la fin
recommencer au début de la boucle extérieure
poser i := i+1 ;
# Q est irréductible, on n’y touche plus
renvoyer L
L’implémenter (on écrira une procédure Berlekamp1:=proc(P,p) renvoyant
la liste formatée [λ, [P 1 , 1], . . . , [P r , 1]] des facteurs irréductibles unitaires de
multiplicité 1, précédés du coefficient dominant) et le tester avec P = x 4 + 1
et p = 3, 17. Comparer avec le résultat de la commande Factors.
254
le noyau de B − I 4 . Comparer la dimension de ce noyau aux nombres de facteurs irréductibles dans la décomposition sur F 3 . Tester la conjecture que cela
suscite à l’aide d’une procédure test:=proc(P,p) et de polynômes tirés au hasard par randpol. Enfin, démontrer au papier-crayon, pour tout P =
r
i=1 P i ,
que la sous-algèbre de Berlekamp N de A, noyau de ϕ p − Id n , est isomorphe à
F r
p , via le morphisme a → (a mod P 1 , . . . , a mod P r ) du théorème Chinois.
4. Soit S une F p -base de N . Écrire une procédure Vect2Pol:=proc(v) convertissant un vecteur v = (y 1 , . . . , y n ) ∈ F r
p en le polynôme
n
i=1 y i x i−1 . En déduire
S sur l’exemple P = x 4 + 1 et p = 3.
On note S = {1, v 1 , . . . , v r−1 }. Si r 2, démontrer qu’il existe, pour tout
1 i, j r, i = j, un élément α ∈ F p et un indice 1 k r − 1 tels que
v k ≡ α mod P i et v k ≡ α mod P j (raisonner par l’absurde : si l’on avait
v k ≡ α k mod P i et v k ≡ α k mod P j pour tout 1 k r − 1, exhiber
une contradiction en regardant dans la base S un élément a tel que a ≡ 1
mod P i et a ≡ 0 mod P j ). En déduire que si Q est un diviseur de P non
irréductible, alors il existe un élément α ∈ F p et un indice 1 k r − 1 tels
que pgcd(v k − α, Q) soit un diviseur strict de Q.
Finalement, démontrer que l’algorithme suivant factorise P :
on pose i := 1 ; L := [P ] ;
# liste de polynômes dont le produit
est P
tant que longueur(L) < r
on prend Q := L[i] ;
pour tout k r − 1, α ∈ F p
on pose D := pgcd(v k − α, Q) ;
si 0 < degré(D) < degré(Q),
remplacer Q par D dans L et rajouter Q/D à la fin
recommencer au début de la boucle extérieure
poser i := i+1 ;
# Q est irréductible, on n’y touche plus
renvoyer L
L’implémenter (on écrira une procédure Berlekamp1:=proc(P,p) renvoyant
la liste formatée [λ, [P 1 , 1], . . . , [P r , 1]] des facteurs irréductibles unitaires de
multiplicité 1, précédés du coefficient dominant) et le tester avec P = x 4 + 1
et p = 3, 17. Comparer avec le résultat de la commande Factors.
254