# Thread: Square root modulo a prime

1. ## Square root modulo a prime

Hello

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.

So -

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.

Thanks!

2. Hi,

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

3. Thanks for the reply. I'm reading that now. Seems complicated!

Do you understand it?

4. There is a way to determine if a number is a square root mod a prime.
That is part of the law of quadradic reciprocity.
But as far as actually find that square, I do not think there are known methods, only algorithms.