Algorithme LLL et factorisation
Bonjour à tous !!
Je cherche un "bon" article ou papier sur le net qui explique les principes de l'algorithme de factorisation en temps polynomial d'un polynôme à coefficients rationnels. Il est basé sur l'algorithme LLL.
Quelqu'un a-t-il vu un tel papier traîner ?
En vous souhaitant un bon dimanche !
Je cherche un "bon" article ou papier sur le net qui explique les principes de l'algorithme de factorisation en temps polynomial d'un polynôme à coefficients rationnels. Il est basé sur l'algorithme LLL.
Quelqu'un a-t-il vu un tel papier traîner ?
En vous souhaitant un bon dimanche !
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Une recherche google rapide me donne ça par exemple : http://www.math.ens.fr/enseignement/telecharger_fichier.php?fichier=527
Tu le sais sans doutes, sinon ça te donnera quelques mots clés: le principe est de factoriser le polynome modulo un premier $p$ bien choisi grâce à l'algorithme de Berlekamp. Ensuite on "remonte" la factorisation modulo des puissance $p^k$. Cette étape se base sur le lemme de Hensel. Enfin un facteur dans $\Z/p^k\Z[x]$ pour $k$ suffisamment grand donne un facteur dans $\Z[x]$. Il me semble que c'est là qu'on utilise LLL.
J'étais passé à côté :?
Bonne soirée !