# 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]=[0],[1]$ or $[4]$, but no solution $[x]$ exists if $[y]=[2]$ or $[3]$. 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.

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