CS547A 2000 Questions and Answers
Questions asked in class
(19/9/00)
fixed (20/9/03) after Payam Shodjai's comment.
Q:
If we have a solution r to r2 = x (mod p), how do we find a solution s to s2 = x (mod pe) for e>1 ?
A:
The chinese remainder theorem does not apply here. We have to figure things out.
First, consider the case e=2. Since r2 = x (mod p), there exists an integer m such that
r2 - x = mp where m = (r2 - x)/p
Suppose the solution mod p2 is of the form s=r+kp for some integer k. Let's expand s2
s2 = (r+kp)2 = r2 + 2rkp + (kp)2 = mp + x + 2rkp + (kp)2
and therefore
s2 = x + (m+2rk)p (mod p2)
We find the solution s by making m+2rk a multiple of p so that (m+2rk)p = 0 (mod p2) :
k = -m*(2r)-1 mod p
and thus
s = r - (m*(2r)-1 mod p)p
and thus
s = r + (x-r2)*((2r)-1 mod p)
Second, notice that the same exact reasoning allows to go from the case e to the case 2e,
meaning that any solution r to r2 = x (mod pe), can be transformed to a solution s=r+kpe to s2 = x (mod p2e).
Using this argument i times allows to start from a solution r to r2 = x (mod p),
and find a solution s to s2 = x (mod pe) for e=2i.
Finally, to solve the general problem where e is not necessarily a power of 2, let i be the smallest integer such that 2i=e'>=e.
From a solution r to r2 = x (mod p), find a solution to s2 = x (mod pe') and since pe|pe' this same solution s will work mod pe.