Algorithm for finding roots of a polynomial modulo prime powers

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?

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