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 **r ^{2} = x (mod p)**, how do we find a solution

A:

The chinese remainder theorem does not apply here. We have to figure things out.

First, consider the case **e=2**. Since **r ^{2} = x (mod p)**, there exists an integer

**r ^{2} - x = mp **where

Suppose the solution **mod p ^{2}** is of the form

s^{2} = (r+kp)^{2} = r^{2} + 2rkp + (kp)^{2 }= mp + x + 2rkp + (kp)^{2}

and therefore

s^{2} __=__ x + (m+2rk)p (mod p^{2})

We find the solution **s** by making **m+2rk** a multiple of **p **so that** (m+2rk)p = 0 (mod p^{2}) **:

**k = -m*(2r) ^{-1} mod p**

and thus

**s = r - (m*(2r) ^{-1} mod p)p**

and thus

**s = r + (x-r ^{2})*((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 **r ^{2} = x (mod p^{e})**, can be transformed to a solution

Using this argument **i** times allows to start from a solution **r** to **r ^{2} = x (mod p)**,

and find a solution **s** to **s ^{2} = x (mod p^{e})** for

Finally, to solve the general problem where **e** is not necessarily a power of **2**, let **i** be the smallest integer such that **2 ^{i}=e'>=e**.

From a solution **r** to **r ^{2} = x (mod p)**, find a solution to