While looking for an answer to your question, I found this link : Square roots
I'm still reading it, but it looks quite interesting with an overall view...
I hope someone can help me with this.
I have the following equation -
y^2 mod 269 = x^3 + 3*x + 5 mod 269
Let's say x is 64.
y^2 mod 269 = 64^3 + 3*64 + 5 mod 269
y^2 mod 269 = 262144 + 192 + 5 mod 269
y^2 mod 269 = 262341 mod 269
y^2 mod 269 = 66
Now, I happen to know off hand that y is 55, but if I didn't know this, how would I calculate y?
I've been told it's as simple as "square root modulo a prime", but I cannot figure out how to do this.
Can someone please explain this to me in simple steps?
Any help appreciated.