Given a polynomial with integer coefficients, determine all of its rational roots. What is the computational complexity of this problem? At first glance, it seems one must factor the leading coefficient and constant term, but maybe there are tricks of solving the polynomial in floating point using for example Newton's Method, then testing whether each found solution is a rational number.
Given a monic polynomial, determine all of its integer roots. Determine all of its Gaussian integer roots. Monic polynomial with Gaussian integer coefficients.