Find a root of a polynomial modulo 2^r [closed]
Want to improve this question? Update the question so it's on-topic for Stack Overflow.
Closed 12 years ago.
Improve this questionI 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
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
.
精彩评论