Find a root of a polynomial modulo 2^r

Question

I have a polynomial P and I would like to find y such that P(y) = 0 modulo 2^r.

I have tried something along the lines of Hensel lifting, but I don't know if this could even work, because of the usual condition f'(y mod 2) != 0 mod 2 which is not usually true.

Is there a different algorithm available ? Or could a variation of Hensel lifting work ?

Thanks in advance

Answer 1

Suppose you have a solution a such that f(a) = 0 mod 2^p. To do a Hensel lift to obtain a solution mod 2^(p+1), you end up needing to solve

f'(a)*t = -f(a)/2^(p+1) mod 2

for t.

If f'(a) = 0 mod 2, there are two possibilities:

if 2 does not divide f(a)/2^(p+1), then there are no solutions mod 2^(p+1) (or any higher power of 2) resulting from this value of a.

If 2 divides f(a)/2^(p+1), then both 0 and 1 work as acceptable values of t, and you'll want to do a separate lift for each of them if you wish to find all solutions mod 2^r.

Note that a is in the range [0,2^p) at each step, so when you solve for t, you're evaluating f(x) and f'(x) at x=a, not x=a mod 2.