How do you solve y=x^2 mod N

  • Thread starter jostpuur
  • Start date
  • #1
2,111
17

Main Question or Discussion Point

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

[tex]
y=x^2\quad \textrm{mod}\quad N ?
[/tex]

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

Answers and Replies

  • #2
34,039
9,881
For prime N, there is an algorithm. The article also has a link for the other cases.
 
  • #3
473
13
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:

Related Threads on How do you solve y=x^2 mod N

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
5
Views
3K
Replies
3
Views
629
Replies
18
Views
1K
  • Last Post
Replies
4
Views
718
  • Last Post
Replies
4
Views
985
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
6
Views
2K
Replies
7
Views
19K
Top