- #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.

[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.