Square root modulo a prime

AARRRGH

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!

LeixlipRed

Try googling quadratic residues.

hivizman

If a is a solution to y^2=x mod p, then so is (p-a). So as well as 55, a solution to the equation y^2=66 mod 269 is 214 (214^2 = 45796 = 269*70 + 66).

In general, there isn't a closed form formula to calculate a square root modulo a prime, but there are some special cases. Fortunately, the prime number 269 fits into one of these cases: p = 8*k+5. For p=269, k=33. To calculate the square root of q mod 269, check whether q^(2*k+1) = 1 mod 269. I used Excel for this, and confirmed that 66^67=1 mod 269. When this holds, a square root of q mod p is q^(k+1). 66^34 mod 269 is 214. The other square root is thus 269-214 = 55.

This all comes from http://mathworld.wolfram.com/QuadraticResidue.html, which is the first item that comes up if you Google "quadratic residue".

idunnoutellme

you find it using the discreet logarithm problem methinks. thats taking logs across so that you can bring the powers down and then its calculated mod p-1

hivizman

Yes, it's a special case of the discrete logarithm problem. This is the problem of finding x, given g and h, such that g^x = h mod p. The method I used for the square root problem was to find k such that h^(2k+1) = 1 mod p. Then it follows that h^(2k+2) = h mod p (multiplying both sides by h). But h^(2k+2)=(h^(k+1))^2, so h^(k+1) is the square root of h mod p. This only works, though, if p can be expressed in the form 8k+5, which it can for p=269.

However, I don't think that there's a general solution for the discrete logarithm problem, so it has to be solved algorithmically in most cases.