Algèbre T1
alors la factorisation dans F p en une décomposition dans Z/p n Z grâce au « lemme
de Hensel ». Le lecteur intéressé trouvera dans [28], chapitre 15, une description
de cette seconde méthode modulaire, ainsi qu’une discussion de la pertinence des
deux méthodes en fonction des paramètres du problème.
☞ Quelques remarques concernant la manipulation des polynômes modulo p
en Maple : par rapport aux commandes relatives aux polynômes de Z[x] et
Q[x], les noms sont en général conservés, mais les commandes commencent par
une majuscule et se terminent par mod p. On utilisera donc Expand(P) mod p
pour développer, Gcd(P,Q) mod p pour le calcul du pgcd, Quo(A,B,x) mod p et
Rem(A,B,x) mod p pour le quotient et le reste de la division euclidienne. Le degré
s’obtient encore par degree(P,x), le coefficient de degré i par coeff(P,x,i) et
le coefficient dominant simplement via lcoeff.
Corps finis et irréductibles de F p [x]
Nous avons besoin, pour effectuer la factorisation dans F p [x], d’un test d’irréductibilité. Nous allons donner un tel critère et en profiter pour indiquer comment
construire de manière effective les corps finis F p n (ils seront étudiés en détail au
chapitre XV, où on les définit à l’aide d’une clôture algébrique de F p , ce qui
démontre l’existence et l’unicité de ces corps, mais n’explique pas comment on
calcule, en pratique, dans les corps finis). En effet, si P est un polynôme irréductible de degré n, alors l’idéal (P ) qu’il engendre est un idéal premier, donc
maximal, de F p [x] (en vertu de la principalité de F p [x]). Le quotient F p [x]/(P )
est donc un corps et un F p -espace vectoriel de base 1, x, . . . , x n−1 , où n = deg P ,
c’est-à-dire un corps à p n éléments.
Proposition 1. Pour qu’un polynôme P ∈ F p [x] de degré n 1 soit irréductible, il
faut et il suffit qu’il satisfasse aux deux conditions suivantes :
(i) P divise x p n − x.
(ii) Pour tout diviseur strict d de n, P ne divise pas x p d − x.
Démonstration. Considérons les degrés des facteurs irréductibles de P . En vertu
du lemme ci-dessous, la condition (i) signifie que ce sont tous des diviseurs de
n et la condition (ii) qu’aucun d’entre eux n’est un diviseur strict de n. Il n’y
a donc qu’un seul facteur irréductible et il est de degré n ; autrement dit, P est
irréductible.
Lemme 1. Soit n 1 un entier. Le polynôme x p n − x ∈ F p [x] est exactement le
produit de tous les polynômes irréductibles unitaires de F p [x] de degré divisant n.
250
alors la factorisation dans F p en une décomposition dans Z/p n Z grâce au « lemme
de Hensel ». Le lecteur intéressé trouvera dans [28], chapitre 15, une description
de cette seconde méthode modulaire, ainsi qu’une discussion de la pertinence des
deux méthodes en fonction des paramètres du problème.
☞ Quelques remarques concernant la manipulation des polynômes modulo p
en Maple : par rapport aux commandes relatives aux polynômes de Z[x] et
Q[x], les noms sont en général conservés, mais les commandes commencent par
une majuscule et se terminent par mod p. On utilisera donc Expand(P) mod p
pour développer, Gcd(P,Q) mod p pour le calcul du pgcd, Quo(A,B,x) mod p et
Rem(A,B,x) mod p pour le quotient et le reste de la division euclidienne. Le degré
s’obtient encore par degree(P,x), le coefficient de degré i par coeff(P,x,i) et
le coefficient dominant simplement via lcoeff.
Corps finis et irréductibles de F p [x]
Nous avons besoin, pour effectuer la factorisation dans F p [x], d’un test d’irréductibilité. Nous allons donner un tel critère et en profiter pour indiquer comment
construire de manière effective les corps finis F p n (ils seront étudiés en détail au
chapitre XV, où on les définit à l’aide d’une clôture algébrique de F p , ce qui
démontre l’existence et l’unicité de ces corps, mais n’explique pas comment on
calcule, en pratique, dans les corps finis). En effet, si P est un polynôme irréductible de degré n, alors l’idéal (P ) qu’il engendre est un idéal premier, donc
maximal, de F p [x] (en vertu de la principalité de F p [x]). Le quotient F p [x]/(P )
est donc un corps et un F p -espace vectoriel de base 1, x, . . . , x n−1 , où n = deg P ,
c’est-à-dire un corps à p n éléments.
Proposition 1. Pour qu’un polynôme P ∈ F p [x] de degré n 1 soit irréductible, il
faut et il suffit qu’il satisfasse aux deux conditions suivantes :
(i) P divise x p n − x.
(ii) Pour tout diviseur strict d de n, P ne divise pas x p d − x.
Démonstration. Considérons les degrés des facteurs irréductibles de P . En vertu
du lemme ci-dessous, la condition (i) signifie que ce sont tous des diviseurs de
n et la condition (ii) qu’aucun d’entre eux n’est un diviseur strict de n. Il n’y
a donc qu’un seul facteur irréductible et il est de degré n ; autrement dit, P est
irréductible.
Lemme 1. Soit n 1 un entier. Le polynôme x p n − x ∈ F p [x] est exactement le
produit de tous les polynômes irréductibles unitaires de F p [x] de degré divisant n.
250