Séminaire du 29 mars 04, Grégoire Lecerf.

Sur la factorisation des polynômes à deux variables

Nous abordons quelques questions de complexit{\'e} autour de la factorisation des polyn{\^o}mes {\`a} deux variables. Dans la lign{\'e}e algorithmique initi{\'e}e par Zassenhaus dans les ann{\'e}es 1970, notre approche est bas{\'e}e sur la {\it remont{\'e}e de Hensel} des facteurs, suivie de leur recombinaison. Nous montrons que la remont{\'e}e des facteurs jusqu'{\`a} une pr{\'e}cision \emph{lin{\'e}aire} en le degr{\'e} total du polyn{\^o}me {\`a} factoriser suffit pour ramener la phase de recombinaison {\`a} un calcul d'alg{\`e}bre lin{\'e}aire. Ainsi, le co{\^u}t total de la remont{\'e}e de Hensel et de la recombinaison des facteurs reste sous-quadratique dans la taille, en repr{\'e}sentation dense, du polyn{\^o}me d'entr{\'e}e. Ceci am{\'e}liore tous les r{\'e}sultats connus sur la complexit{\'e} de la factorisation des polyn{\^o}mes {\`a} deux variables. L'{\'e}tape de remont{\'e}e se r\'ev\`ele souvent le goulot d'{\'e}tranglement de cette m{\'e}thode. Nous proposons un nouvel algorithme bas{\'e} sur le calcul des {\it r{\'e}ductions modulaires simultan{\'e}es} d'un polyn{\^o}me {\`a} une variable et prouvons que sa complexit{\'e} am{\'e}liore le meilleur algorithme connu pour la remont{\'e}e. D'un point de vue pratique, notre implantation permet de traiter le $11$-{\`e}me polyn{\^o}me de Swinnerton-Dyer d{\'e}fini sur le corps fini $k=\mathbb{Z}/754974721\mathbb{Z}$ \, en environ $30$ minutes. Ce polyn{\^o}me comporte plus de $500000$ mon{\^o}mes et la preuve de son irr{\'e}ductibilit{\'e} sur $k[x,y]$ n'{\'e}tait pr{\'e}c{\'e}demment accessible {\`a} aucun des logiciels de calcul formel. Ces r{\'e}sultats ont {\'e}t{\'e} obtenus en collaboration avec A.~Bostan, B.~Salvy, {\'E}.~Schost et B.~Wiebelt.