1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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