Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How do you solve y=x^2 mod N

  1. Dec 19, 2014 #1
    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.
     
  2. jcsd
  3. Dec 19, 2014 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    For prime N, there is an algorithm. The article also has a link for the other cases.
     
  4. Dec 19, 2014 #3
    You're talking about quadratic residues.
    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: Dec 19, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook