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