Given a polynomial $f$ with integer coefficients and a prime power $p^i$, I wish to find a root of $f$ modulo $p^i$, provided one exists, in polynomial or randomized polynomial time in the size of the input.

A simple idea would be to use Cantor-Zassenhaus' algorithm to find a root modulo $p$, and then lift it by Hensel's lemma. But then, this would work only when $f'$ isn't zero. Is there a way where we can get past this barrier?

  • 1
    $\begingroup$ If you're fluent in French, you may want to take a look at number 96 here. $\endgroup$ – xavierm02 Mar 3 '17 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.