Algèbre T1
Puisque l’on dispose d’un algorithme efficace de factorisation sur F p
(TP.IX.A), le corollaire précédent fournit une méthode de construction des corps
finis F p r , alternative à celle exposée au TP.IX.A où le polynôme irréductible de
degré r était obtenu par tirage aléatoire. Cependant, Φ p r −1 est de degré ϕ(p r − 1),
qui est exponentiel en r : c’est impratiquable pour r très grand.
1. Écrire une procédure cyclo:=proc(n) calculant Φ n en suivant l’algorithme
exposé ci-dessus. Tester avec n = 3 4 − 1 et comparer avec le résultat de la
commande Maple numtheory[cyclotomic](3^4-1,x).
2. Vérifier que P = x 4 − x 3 + x 2 − x + 1 est irréductible sur F 3 à l’aide de la
commande Irreduc(P) mod 3. Si a désigne une racine de P dans une clôture
algébrique F 3 , le corps F 3 (a) F 3 [x]/(P ) est donc un corps fini à 3 4 éléments.
Tester sous Maple :
> alias(a=RootOf(P) mod 3):
> Normal(a^9) mod 3;
> Normal(a^(-1))) mod 3;
et comparer avec les résultats des calculs menés dans F 3 [x]/(P ), où a correspond à la classe de x (commandes Rem pour le reste d’une division euclidienne
et Gcdex pour obtenir l’inverse modulaire, c’est-à-dire les coefficients de Bezout
calculés selon l’algorithme d’Euclide étendu).
3. Nous allons maintenant apprendre à décomposer en irréductibles dans F q [x].
L’algorithme de Berlekamp exposé au sein du TP.IX.A réalise cette tâche (bien
que nous ayons supposé q = p pour simplifier ; le lecteur motivé saura adapter
les énoncés).
– Vérifier que P 1 = x 3 + 2x 2 + 2x + 1 est décomposé sur F 3 , à l’aide de la
commande Factor(P) mod 3.
– Démontrer qu’un corps de rupture de P 2 = x 3 + 2x 2 − x − 1 sur F 3 est
corps de décomposition. On factorisera P 2 sur F 3 (a), où a est défini par
une commande RootOf, en invoquant Factor(P2,a) mod 3.
– Factoriser P 3 = x 4 + 2x 3 + 2x 2 + x + 2 sur F 9 . Déterminer un corps de
rupture et un corps de décomposition. On utilisera les polynômes cyclotomiques (cf. corollaire 2) pour construire les corps finis F 3 r .
4. Vérifier que les facteurs irréductibles de Φ 3 4 −1 sur F 3 k , 1 k 4, sont bien du
degré prescrit par la proposition 2, sachant que l’ordre de q dans U(Z/nZ) s’obtient avec la commande Maple numtheory[order](q,n). Il est clair, au vu
390
Puisque l’on dispose d’un algorithme efficace de factorisation sur F p
(TP.IX.A), le corollaire précédent fournit une méthode de construction des corps
finis F p r , alternative à celle exposée au TP.IX.A où le polynôme irréductible de
degré r était obtenu par tirage aléatoire. Cependant, Φ p r −1 est de degré ϕ(p r − 1),
qui est exponentiel en r : c’est impratiquable pour r très grand.
1. Écrire une procédure cyclo:=proc(n) calculant Φ n en suivant l’algorithme
exposé ci-dessus. Tester avec n = 3 4 − 1 et comparer avec le résultat de la
commande Maple numtheory[cyclotomic](3^4-1,x).
2. Vérifier que P = x 4 − x 3 + x 2 − x + 1 est irréductible sur F 3 à l’aide de la
commande Irreduc(P) mod 3. Si a désigne une racine de P dans une clôture
algébrique F 3 , le corps F 3 (a) F 3 [x]/(P ) est donc un corps fini à 3 4 éléments.
Tester sous Maple :
> alias(a=RootOf(P) mod 3):
> Normal(a^9) mod 3;
> Normal(a^(-1))) mod 3;
et comparer avec les résultats des calculs menés dans F 3 [x]/(P ), où a correspond à la classe de x (commandes Rem pour le reste d’une division euclidienne
et Gcdex pour obtenir l’inverse modulaire, c’est-à-dire les coefficients de Bezout
calculés selon l’algorithme d’Euclide étendu).
3. Nous allons maintenant apprendre à décomposer en irréductibles dans F q [x].
L’algorithme de Berlekamp exposé au sein du TP.IX.A réalise cette tâche (bien
que nous ayons supposé q = p pour simplifier ; le lecteur motivé saura adapter
les énoncés).
– Vérifier que P 1 = x 3 + 2x 2 + 2x + 1 est décomposé sur F 3 , à l’aide de la
commande Factor(P) mod 3.
– Démontrer qu’un corps de rupture de P 2 = x 3 + 2x 2 − x − 1 sur F 3 est
corps de décomposition. On factorisera P 2 sur F 3 (a), où a est défini par
une commande RootOf, en invoquant Factor(P2,a) mod 3.
– Factoriser P 3 = x 4 + 2x 3 + 2x 2 + x + 2 sur F 9 . Déterminer un corps de
rupture et un corps de décomposition. On utilisera les polynômes cyclotomiques (cf. corollaire 2) pour construire les corps finis F 3 r .
4. Vérifier que les facteurs irréductibles de Φ 3 4 −1 sur F 3 k , 1 k 4, sont bien du
degré prescrit par la proposition 2, sachant que l’ordre de q dans U(Z/nZ) s’obtient avec la commande Maple numtheory[order](q,n). Il est clair, au vu
390