# Square root algorithm in modulo $n = pq$

I've been stuck in this problem quite a bit.

I have to find an efficient algorithm wich, given: $$p = 4k+3\\ q = 4m+3\\ p,q \hspace{2mm} \text{odd primes}\\ a\in \mathbb{N}$$

verifies if there exists some$\ b$ such that, $$b^2 \equiv a\pmod n,\quad n=pq,\quad b\in \mathbb{N}$$

Something useful might be the following property, wich has already been proven: $$b^2 \equiv a\pmod n,\hspace{2mm} n=pq \Leftrightarrow c^2 \equiv a\pmod q \wedge d^2 \equiv a\pmod p$$

but I'm not quite sure how to use that information.

All my approaches have been unsuccesful and I haven't been able to use the fact that $\ p$ and $\ q$ have a given form of$\ (4k + 3)$.

All help is appreciated.

• Are you familiar with Euler's Criterion? For that, the fact that the primes are of the form $4k+3$ is not relevant. – André Nicolas Nov 11 '13 at 5:43
• Maybe you can look up the Quadratic Reciprocity Law. – wannadeleteacct Nov 11 '13 at 5:45

## 1 Answer

Hint: If you use Euler's Criterion as suggested by André Nicolas and find that $a$ has square roots mod p, you know that $a^{\frac{p-1}{2}} \equiv 1 \pmod p$. Now set $r := a^{\frac{p+1}{4}} \pmod p$, and compute $r^2 \pmod p$. This uses the fact, that $p=4 k + 3$ and is effective if you have an effective modular exponentiation algorithm. If $a$ has square roots mod $p$ and $q$, then use the Chinese remainder theorem to get square roots mod $n$.