Small Roots of Modular Equations
James H. Davenport · 2009
I started out with a polynomial of degree k, often with smallcoecients, and now I have one of degree hk with largercoecients!But the root is now over the integers. This gives us two strategies.Integer roots correspond to factors of the trailing coecients(often cheap in practice).Factor modulo some small p and Hensel lift the linear factors(guaranteed non-dominant complexity).As h !1, X !2