Racines entières d'un polynôme

Quel algorithme pouvons-nous utiliser pour trouver toutes les racines entières d'un polynôme avec des coefficients entiers?$f(x)$

J'observe que Sage peut trouver les racines en quelques secondes même lorsque tous les coefficients de sont très grands. Comment est-il capable de faire cela?$f(x)$

En supposant que les coefficients de sont des entiers ou des rationnels et que vous voulez des racines entières, l'approche la plus simple est d'utiliser le théorème de la racine entière ou rationnelle. Voir http://en.wikipedia.org/wiki/Rational_root_theorem Comme indiqué par DW, cela pourrait être problématique si le coefficient constant est difficile à factoriser (voir aussi /math/123018/polynomial- et-entier-racines )$f$

Dans tous les cas, la documentation de Sage explique clairement comment ils effectuent la recherche racine: "La méthode suivante, qui est utilisée si K est un domaine intégral, est d'essayer de factoriser le polynôme. Si cela réussit, alors pour chaque degré un facteur a * x + b, nous ajoutons -b / a en tant que racine (tant que ce quotient est réellement dans l'anneau souhaité). " Voir http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html .

Votre question devient alors: Comment factorisent-ils efficacement les polynômes avec des coefficients entiers? Apparemment, Sage appelle NTL pour ce faire (voir http://www.shoup.net/ntl/doc/ZZXFactoring.txt pour les détails NTL).

Si vous voulez une méthode efficace asymptotiquement, vous pouvez vous référer à la méthode de Lenstra, Lenstra et Lovasz ( https://openaccess.leidenuniv.nl/handle/1887/3810 ).