Preparation Agregation Externe UPMC Matthieu Romagny

Factorisation des polynones sur les corps finis

1 L'algorithne de Berlekanp
Soit K = Fq un corps fini, et soit P ∈ K[X] un polynome. On souhaite factoriser P ;
l'algorithme de Berlekamp prend P en entree, et ressort soit P si celui-ci est irreductible,
soit un diviseur non trivial de P . Les etapes sont les suivantes :
(1) si P t = 0 alors il existe Q tel que P (X) = Q(Xp). Soit R le polynome dont les coefficients
sont les racines des coefficients de Q (bien determines car le Frobenius F est un isomorphisme
de K), alors P (X) = (R(X))p et l'algorithme renvoie R et s'arrete.
(2) si P ∧ P t /= 1 alors c'est un facteur non trivial de P donc l'algorithme renvoie P ∧ P t
et s'arrete.
(3) sinon, P a ses facteurs irreductibles distincts. Soit A = K[X]/P qui est une K-
algebre de dimension n, et considerons l'endomorphisme de K-ev F − Id. Soit r la
dimension de N = ker(F − Id) ; on a r ≥ 1 car K ⊂ N . Si r = 1 alors P est
irreductible, l'algorithme le dit et s'arrete. Si r ≥ 2 on prend un element de N \ K, classe d'un
polynome Q ∈ K[X]. On decrit alors tous les α ∈ K et on calcule le pgcd de P et Q − α.
Un lemme montre que pour
un certain α on trouve un truc non trivial, l'algorithme le renvoie et s'arrete.

2 Mise en pratique
Voici une question (hyper classique) posee a l'oral 2005 dans la lecon sur les racines des
polynomes : factoriser P = X9 + X6 − X + 1 sur K = F3.
La premiere chose a faire est de voir s'il a une racine dans K. C'est vite fait car K n'a que
3 elements, et on trouve qu'il n'y a pas de racine. Appliquons maintenant l'algorithme :
(1) P t = −1.
(2) P ∧ P t = 1 car P t = −1.
(3) On est donc dans le vif du sujet. L'algebre qui nous interesse est
A = K[X]/(X9 + X6 − X + 1) .
C'est un K-ev de dimension 9 dont une base est {1, X, X 2 , . . . , X8}. Pour calculer la
matrice de l'endomorphisme F − Id on aura besoin des puissances de X3 jusqu'a X24. Je vais
calculer aussi X10 et X11, vous verre'. tout de suite pourquoi en suivant le calcul :
X910= −X67+ X − 1
X11 = −X8 + X23 − X
X2 = −X + X −
X
X12 = −(−X6 + X − 1) + X4 − X3 = X6 + X4 − X3 − X + 1
X15 = (−X6 + X − 1) + X7 − X6 − X4 + X3 = X7 + X6 − X4 + X3 + X − 1
X18 = (−X7 + X2 − X) + (−X6 + X − 1) − X7 + X6 + X4 − X3 = X7 + X4 − X3 + X2
−1
X21 24
= (−X7 + X2 − X) + X7 − X6 + X5 − X3 = −X6 + X5 − X3 + X2 −
X X = −(−X6 + X − 1) + X8 − X6 + X5 − X4 = X8 + X5 − X4 − X +
1

1
On peut alors ecrire la matrice de F − Id
: 
1
 X
0 0 0 −1 1 −1 −1 0 1 
2
 0 −1 0 1 −1 1 0 −1 −1  X
 0 0 −1 0 0 0 1 1 0  X3
 0 1 0 −1 −1 1 −1 −1 0  X4
 0 0 0 0 0 −1 1 0 −1 X
5

 0 0 0 0 0 −1 0 1 1 
 6
 0 0 1 −1 1 1 −1 −1 0  XX7
 0 0 0 0 0 1 1 −1 0
0 0 0 0 0 0 0 0 0 X8

Le noyau contient la droite engendree par la premiere colonne ; il faut decider s'il est plus
gros. Utilisons le pivot de Gauss ; c'est long mais on trouve le vecteur (0, 1, −1, −1, 1, 1,
−1, 0, 1) (par exemple). Un representant polynome est
Q(X) = X8 − X6 + X5 + X4 − X3 − X2 + X
On calcule ensuite P ∧ (Q − α). Gardons α general au debut, on fera α = 0, 1 ou 2 en temps
utile. On utilise l'algorithme d'Euclide : la premiere division est

X9 + X6 − X + 1 = (X8 − X6 + X5 + X4 − X3 − X2 + X − α)X + (X7 − X5 + X4 + X3 − X2 + (α −

1)X + 1)

La seconde est

X8 − X6 + X5 + X4 − X3 − X2 + X − α = (X7 − X5 + X4 + X3 − X2 + (α − 1)X + 1)X − α(X2 +

1)

C'est gagne car si α = 0, on a un reste nul, donc X7 − X5 + X4 + X3 − X2 − X + 1 divise P

:
P (X) = (X7 − X5 + X4 + X3 − X2 − X + 1)(X2 + 1)
On pourrait imaginer de continuer l'algorithme avec α /= 0, mais on ne trouverait rien d'autre
(je ne sais pas si c'est un fait general de l'algorithme de Berlekamp), car on poursuivrait avec
X2 + 1 comme reste, or on sait deja qu'il divise P .
Le polynome X2 + 1 est irreductible sur F3. Il faut ensuite recommencer avec le facteur
P1 = X7 − X5 + X4 + X3 − X2 − X + 1. Avec moins de detail cette fois :

Matrice de F − Id
7 5
X =X −X −X +X +X−14 3 2 
 0 0 0 −1 1 1 1 1
X9 = −X6 + X − 1
0 −1 0 1 −1 −1 1  X
0 0 −1 0 0 1 −1 X2
X12 = + − X3 − X + 1  0 1 0 −1 −1 0 1 
X 6
X 4 X3
X15 = X6 + X5 + X4 + X2 − X + 1  0 0 0 0 0 1 0 
0 0 0 0 0 0 1 4
X18 = + − X2 0 0 1 −1 1 1 −1  X
+X+1  
X5 X3 X5
X6
Ici on voit tres rapidement que le systeme forme par les six colonnes de droite est de rang
maximal, donc la dimension du noyau est 1 et P est irreductible. En conclusion la decomposition
en facteurs irreductibles de X9 + X6 − X + 1 est (X7 − X5 + X4 + X3 − X2 − X + 1)(X2
2
+ 1).

3
3 Deconposition sur les exenples sinples
Dans les cas simples, soit on aura une racine dans le corps de base, soit il y aura suffisamment
de facteurs irreductibles de petit degre (i.e. 2 ou 3) qui sont facilement detectables et
permettent de conclure. Dans ce cas-la, on "va a la pechen ce qui necessite tout de meme de la
methode.
Rappelons tout d'abord la remarque utile :
Lemme Soit K Un corps et P ∈ K[X] de degre n. Alors P est redUctible ssi il est
divisible p r Un polynome de degre ≤ n/2.
D'abord notons qu'il est facile de tester si un polynome de degre ≤ 3 est irreductible, car
cela equivaut a dire qu'il n'a pas de racine. On voit alors, par exhaustion, que sur F3, les
polynomes irreductibles unitaires de degre 2 sont : X2 + 1, X2 + X − 1, X2 − X − 1.

Remarque comme on est en caracteristique differente de 2, a translation pres sur la variable,

dans tout polynome unitaire de degre 2 on peut camoufler le terme en X puisque X2 + aX
= (X +2 1a)2 + . . . Par ailleurs il est clair que P est irreductible ssi P (X + a) l'est. Donc
partant des polynomes irreductibles de degre 2 et sans terme en X (il n'y en a qu'un : X2 +
1), on les
trouve tous en susbtituant X + a (a ∈ F3) a X. On trouve ainsi X2 + X − 1 et X2 − X −
1
sans calcul.
Pour trouver les polynomes irreductibles de degre 3 on peut utiliser le fait que X3 − X
induit la fonctions nulle sur F3. Si P est un polynome irreductible unitaire de degre 3, alors
P − (X3 − X) est un polynome de degre ≤ 2 dont la fonction associee ne s'annulle pas. Il
est
donc de la forme aQ avec a ∈ 3 et Q unitaire sans racine, i.e. egal a 1 ou irreductible de
F×
degre 2. En sens inverse, partant de Q = 1 ou Q de degre 2 unitaire irreductible, le polynome
P = X3 − X + aQ est irreductible unitaire de degre 3. On trouve ainsi :
X3 − X + 1 , (X3 − X) + (X2 + X − 1) = X3 + X2 − 1 ,
X3 − X − 1 , (X3 − X) − (X2 + X − 1) = X3 − X2 + X + 1 ,

(X3 − X) + (X2 + 1) , (X3 − X) + (X2 − X − 1) = X3 + X2 + X − 1 ,

(X3 − X) − (X2 + 1) , (X3 − X) − (X2 − X − 1) = X3 − X2 + 1 .

Remarque verifions que les polynomes trouves sont en nombre correct a l'aide de la
formule
1
card I(n, q) = L
n µ(d)qn/d
d|n
2 3
1×3 +(−1)×3 1×3 +(−1)×3
On trouve card I(2, 3) = = 3 et card I(3, 3) = = 8.
2 3