0
$\begingroup$

if $x^2 \bmod p = q$ and I know $p$ and $q$, how to get $x$?

I'm aware this has to do with quadratic residues but I do not know how to actually solve it. $p$ is a prime of form $4k+3$

  • 1
    There are algorithms for finding square roots when the modulus is prime. E.g.,, the [Tonelli-Shanks algorithm](http://en.wikipedia.org/wiki/Shanks_algorithm). Finding square roots with composite moduli is computationally equivalent to factoring.2012-07-15

2 Answers 2

4

Euler's theorem says that $\left(\frac{q}{p}\right) \equiv q^{\frac{p-1}{2}} \bmod p$. On the other hand, assuming there is a solution, $\left(\frac{q}{p}\right) = 1$.

So you have $q^{\frac{p+1}{2}} \equiv q*q^{\frac{p-1}{2}} \equiv q \bmod p$. Since $p+1$ is divisible by $4$, this gives solutions $x \equiv \pm q^{\frac{p+1}{4}} \bmod p.$

  • 0
    @ArturoMagidin Thanks, I didn't know about that.2012-07-15
0

A finite field of order $\rm\:4n\!+\!3\:$ has subgroup of squares of order $\rm\:2n\!+\!1.\:$ But one easily shows that in any group of odd order $\rm\; 2n\!+\!1\:$ the equation $\rm\; x^2 = a\;$ has solution $\rm\: a^{n+1}\;$ (Lagrange, 1769).

More generally, there are reasonably efficient algorithms to compute square roots mod $\rm\,p,\:$ e.g. the Tonelli-Shanks and Cipolla algorithms.