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

1. Dec 19, 2014

### jostpuur

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.

2. Dec 19, 2014

### Staff: Mentor

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

3. Dec 19, 2014

### Joffan

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$
I Coordinate systems in $\mathbb{R}^2$ Mar 16, 2018