TRAVAUX PRATIQUES
TP.IX.A. Factorisation des polynômes
Vous avez étudié au sein des TR.VIII.A et TR.VIII.B des critères permettant
de vérifier l’irréductibilité de polynômes. Si ces derniers permettent de traiter des
cas de degré arbitrairement grand, ils ne s’appliquent cependant pas à n’importe
quel polynôme que l’on se donne explicitement. Par contre, Maple sait factoriser dans Q[x] (commande factor ou factors, selon l’affichage souhaité) tout
polynôme, pourvu que le degré ne soit pas tel que l’on dépasse les capacités de
la machine. Le but de ce TP est de comprendre et de réimplémenter l’algorithme
qui se cache derrière la commande Maple (ou du moins un algorithme efficace
qui réalise la factorisation).
Quitte à multiplier par un entier suffisamment grand, on peut toujours supposer que le polynôme P appartient à Z[x]. On peut alors réduire P modulo
un nombre premier p et se poser la question de la factorisation du polynôme P
obtenu dans F p [x] (où F p désigne le corps fini Z/pZ). La commande Maple correspondante est Factor(P) mod p (ou Factors(P) mod p). Nous allons décrire
un algorithme de factorisation sur un corps fini, dû à Berlekamp, qui utilise essentiellement de l’algèbre linéaire et le morphisme de Frobenius (cf. TR.IX.A). Pour
simplifier, nous nous limiterons à F p . Signalons également qu’il existe d’autres
algorithmes (Cantor-Zassenhaus, etc.) ; le lecteur trouvera dans [28] une description de ces derniers et une comparaison de leur efficacité en fonction des différents
paramètres du problème.
L’algorithme de factorisation sur Q que nous décrirons est de nature « modulaire » : on factorise P sur F p et l’on reconstruit les facteurs de P dans Z[x] à
partir des facteurs de P . C’est possible grâce à une borne a priori M des coefficients des diviseurs de P (borne de Mignotte) ; on prend alors p > 2M . Nous nous
limiterons au cas d’un seul grand nombre premier. Il existe d’autres variantes :
par exemple, prendre un petit premier p et un entier n tel p n > 2M . On relève
TP.IX.A. Factorisation des polynômes
Vous avez étudié au sein des TR.VIII.A et TR.VIII.B des critères permettant
de vérifier l’irréductibilité de polynômes. Si ces derniers permettent de traiter des
cas de degré arbitrairement grand, ils ne s’appliquent cependant pas à n’importe
quel polynôme que l’on se donne explicitement. Par contre, Maple sait factoriser dans Q[x] (commande factor ou factors, selon l’affichage souhaité) tout
polynôme, pourvu que le degré ne soit pas tel que l’on dépasse les capacités de
la machine. Le but de ce TP est de comprendre et de réimplémenter l’algorithme
qui se cache derrière la commande Maple (ou du moins un algorithme efficace
qui réalise la factorisation).
Quitte à multiplier par un entier suffisamment grand, on peut toujours supposer que le polynôme P appartient à Z[x]. On peut alors réduire P modulo
un nombre premier p et se poser la question de la factorisation du polynôme P
obtenu dans F p [x] (où F p désigne le corps fini Z/pZ). La commande Maple correspondante est Factor(P) mod p (ou Factors(P) mod p). Nous allons décrire
un algorithme de factorisation sur un corps fini, dû à Berlekamp, qui utilise essentiellement de l’algèbre linéaire et le morphisme de Frobenius (cf. TR.IX.A). Pour
simplifier, nous nous limiterons à F p . Signalons également qu’il existe d’autres
algorithmes (Cantor-Zassenhaus, etc.) ; le lecteur trouvera dans [28] une description de ces derniers et une comparaison de leur efficacité en fonction des différents
paramètres du problème.
L’algorithme de factorisation sur Q que nous décrirons est de nature « modulaire » : on factorise P sur F p et l’on reconstruit les facteurs de P dans Z[x] à
partir des facteurs de P . C’est possible grâce à une borne a priori M des coefficients des diviseurs de P (borne de Mignotte) ; on prend alors p > 2M . Nous nous
limiterons au cas d’un seul grand nombre premier. Il existe d’autres variantes :
par exemple, prendre un petit premier p et un entier n tel p n > 2M . On relève