4
$\begingroup$

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.

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

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.