Date: Tue, 9 Feb 1999 00:59:13 +0100 From: "Frederic.Lehobey" To: Pascal.Weil@labri.u-bordeaux.fr Cc: Marie-Francoise.Coste-Roy@univ-rennes1.fr, Annick.Valibouze@lip6.fr Subject: Soumission Ecole Jeune Chercheurs Mime-Version: 1.0 REFORMULATION DU PROBLEME DE REMONTEE DANS LA METHODE DE REMONTEE A LA HENSEL DE COLLINS ET ENCARNACION (FACTORISATION DES POLYNOMES EN UNE VARIABLE A COEFFICIENTS ENTIERS). Bien qu'il existe un algorithme en temps polynomial pour la factorisation des polynomes a coefficients dans les entiers (LLL), le schema classique de Berlekamp-Zassenhaus de complexite exponentielle dans le pire des cas est toujours utilise et implante pour son efficacite pratique sur les problemes accessibles au calcul formel. C'est pourquoi il est toujours interessant de l'ameliorer. Le schema de Berlekamp-Zassenhaus a recemment ete modifie sur les points suivants : detection precoce de vrais facteurs (Wang), utilisation des bornes sur un seul facteur (Beauzamy- Trevisan-Wang) et de nouvelles methodes de remontee des facteurs modulaires (Collins-Encarnacion, Wang). Nous traitons de la reformulation du probleme de remontee lorsque sont trouves au cours du processus de factorisation des << vrais facteurs >> qui ne sont pas forcement irreductibles. Paul S. Wang a propose un algorithme de lemme de Hensel effectif en l'accompagnant d'une reformulation du probleme de remontee dans sa methode. George E. Collins et Mark J. Encarnacion ont propose recemment (1995) un nouvel algorithme de lemme de Hensel effectif mais ils n'indiquent pas comment effectuer la reformulation du probleme de remontee dans leur methode. Or cette reformulation est indispensable pour implanter efficacement leur algorithme. Nous fournissons tous les calculs necessaires pour la reformulation du probleme de remontee dans la methode de Collins et Encarnacion ainsi qu'un etude de complexite qui montre que la reformulation est plus interessante qu'un re-calcul. Nous avons aussi ajoute un procede combinatoire d'enumeration des combinaisons de facteurs modulaires (qui constituent l'etape exponentielle de la factorisation) qui permet d'eviter des calculs superflus.