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.