# How do you solve y=x^2 mod N

Suppose $N=1,2,3,\ldots$ and $y=0,1,2,\ldots, N-1$ are fixed. How do solve $x$ out of

$$y=x^2\quad \textrm{mod}\quad N ?$$

I went through some of the smallest values for $N$ and all $y$, and I could not see a pattern. For example, if $N=5$, then at least one $[x]$ exists if $[y]=,$ or $$, but no solution $[x]$ exists if $[y]=$ or $$. You can produce similar result for other small $N$ with finite amount of work, but I failed to see a pattern that I could try to generalize.

## Answers and Replies

mfb
Mentor
For prime N, there is an algorithm. The article also has a link for the other cases.

You're talking about quadratic residues.
Modulo 2, every integer is a quadratic residue.

Modulo an odd prime number p there are (p + 1)/2 residues (including 0) and (p − 1)/2 nonresidues. In this case, it is customary to consider 0 as a special case

Edit to add: If you just want to determine whether a given k is a solution to ##k \equiv x^2 \text{ mod } p##, for ##p## prime, you can use Euler's criterion: ##k^\frac{p-1}{2} \equiv 1 \text{ mod } p##

Last edited: