Algèbre T1
Soit alors M = P sup 1ddeg(P )/2 sup 1id
d
i
, appelée borne de Mignotte
(ou toute autre constante dont l’on sache que si Q est un diviseur non trivial de
P , alors les coefficients de l’un parmi Q et P/Q sont majorés en valeur absolue
par M ). Choisissons un nombre premier p > 2M ne divisant pas le coefficient
dominant de P et tel que la réduction P modulo p soit sans facteur carré. On
écrit la décomposition P = λ
r
i=1 P i en irréductibles dans F p [x] (où λ désigne le
coefficient dominant de P ).
Si S est un sous-ensemble de {1, . . . , r}, on note P S le polynôme congru à
i∈S P i modulo p dont tous les coefficients sont compris entre −p/2 et p/2 (choisir les représentants de Z/pZ symétriques par rapport à 0, que l’on obtient en
Maple avec l’opérateur mod en définissant au préalable mod:=‘mods‘). Si P n’est
pas irréductible, il s’écrit P = λQR et on a donc QR ≡
r
i=1 P i mod p. Il
existe donc une partition de {1, . . . , r} en deux sous-ensembles I et J tels que
Q ≡ P I mod p et R ≡ P J mod p. L’un des deux, par exemple Q, est de degré
deg(Q) deg(P )/2. En vertu du théorème précédent et du choix de p, Q est égal
à P I dans Z[x].
☞ Autres commandes Maple utiles :
floor (partie entière), binomial, norm(f,2) (pour calculer f ),
convert(S,‘*‘) (pour multiplier entre eux tous les polynômes de la liste S) ;
enfin, si S est une liste de polynômes, combinat[choose](S,i) renvoie la liste
des parties de S à i éléments.
10. Écrire une procédure trouve_p:=proc(f) renvoyant un nombre premier (de
préférence le plus petit) supérieur strictement à 2 fois la borne de Mignotte, ne
divisant pas le coefficient dominant de f et tel que P soit sans facteur carré.
Traiter les exemples suivants :
P = x
6 + 2x
3 + 4x
2 + 15, P = x
9 + x
6 + x
5
− 2x
4
− 2x − 2.
On déterminera p puis l’on testera la divisibilité par des P S , avec S de cardinal
1, puis 2, 3, etc., jusqu’à |S|/2. Lorsqu’un facteur non trivial Q = P S est
obtenu, ne pas oublier d’éliminer les indices correspondants de S avant de
recommencer avec P/Q. En déduire la factorisation en irréductibles dans Q[x]
de ces polynômes.
11. Écrire une procédure FactQ:=proc(P) renvoyant la décomposition en produit
d’irréductibles dans Q[x]. On automatisera les calculs de la question précédente, la décomposition modulo p étant obtenue via Factors(P) mod p. On
éliminera d’emblée les cas triviaux où P est de degré inférieur ou égal à un,
cas où la borne de Mignotte n’est pas définie.
258
Soit alors M = P sup 1ddeg(P )/2 sup 1id
d
i
, appelée borne de Mignotte
(ou toute autre constante dont l’on sache que si Q est un diviseur non trivial de
P , alors les coefficients de l’un parmi Q et P/Q sont majorés en valeur absolue
par M ). Choisissons un nombre premier p > 2M ne divisant pas le coefficient
dominant de P et tel que la réduction P modulo p soit sans facteur carré. On
écrit la décomposition P = λ
r
i=1 P i en irréductibles dans F p [x] (où λ désigne le
coefficient dominant de P ).
Si S est un sous-ensemble de {1, . . . , r}, on note P S le polynôme congru à
i∈S P i modulo p dont tous les coefficients sont compris entre −p/2 et p/2 (choisir les représentants de Z/pZ symétriques par rapport à 0, que l’on obtient en
Maple avec l’opérateur mod en définissant au préalable mod:=‘mods‘). Si P n’est
pas irréductible, il s’écrit P = λQR et on a donc QR ≡
r
i=1 P i mod p. Il
existe donc une partition de {1, . . . , r} en deux sous-ensembles I et J tels que
Q ≡ P I mod p et R ≡ P J mod p. L’un des deux, par exemple Q, est de degré
deg(Q) deg(P )/2. En vertu du théorème précédent et du choix de p, Q est égal
à P I dans Z[x].
☞ Autres commandes Maple utiles :
floor (partie entière), binomial, norm(f,2) (pour calculer f ),
convert(S,‘*‘) (pour multiplier entre eux tous les polynômes de la liste S) ;
enfin, si S est une liste de polynômes, combinat[choose](S,i) renvoie la liste
des parties de S à i éléments.
10. Écrire une procédure trouve_p:=proc(f) renvoyant un nombre premier (de
préférence le plus petit) supérieur strictement à 2 fois la borne de Mignotte, ne
divisant pas le coefficient dominant de f et tel que P soit sans facteur carré.
Traiter les exemples suivants :
P = x
6 + 2x
3 + 4x
2 + 15, P = x
9 + x
6 + x
5
− 2x
4
− 2x − 2.
On déterminera p puis l’on testera la divisibilité par des P S , avec S de cardinal
1, puis 2, 3, etc., jusqu’à |S|/2. Lorsqu’un facteur non trivial Q = P S est
obtenu, ne pas oublier d’éliminer les indices correspondants de S avant de
recommencer avec P/Q. En déduire la factorisation en irréductibles dans Q[x]
de ces polynômes.
11. Écrire une procédure FactQ:=proc(P) renvoyant la décomposition en produit
d’irréductibles dans Q[x]. On automatisera les calculs de la question précédente, la décomposition modulo p étant obtenue via Factors(P) mod p. On
éliminera d’emblée les cas triviaux où P est de degré inférieur ou égal à un,
cas où la borne de Mignotte n’est pas définie.
258