Can anyone think of a simple algorithm to solve this problem?

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 any of you guys think of a simple algorithm I could use to calculate y?

This is doing my head in...

Thanks!

phil

This sounds like you're trying to re-invent some cryptographic wheel without having the appropiate Math background.

square root modulo a prime is a well known problem in cryptography and x^2 mod p where p gets large is not an easy problem to solve.

My advice for you is either:

a. Learn the Maths behind this first, you seem to be skipping to the programming end first. You're starting from the wrong side.

b. Use a proper library to do the crypto for you, especially if this isn't some pet project and the data actually needs to be cryptographically secure.

Giblet

Strange one, y can be multiple values.

Eg: 14.2478068`

AARRRGH

phil wrote: »

This sounds like you're trying to re-invent some cryptographic wheel without having the appropiate Math background.

square root modulo a prime is a well known problem in cryptography and x^2 mod p where p gets large is not an easy problem to solve.

My advice for you is either:

a. Learn the Maths behind this first, you seem to be skipping to the programming end first. You're starting from the wrong side.

b. Use a proper library to do the crypto for you, especially if this isn't some pet project and the data actually needs to be cryptographically secure.

Yeah, I'm aware Koblitz wrote an algorithm for this, but like all Elliptic Curve Cryptography documentation, they couldn't write it in a more abstract, unhelpful style if they tried!

I'm currently using an inefficent brute force system... it'll work for now until I can get my head around Koblitz's stuff.

Thanks for the reply.

IRLConor

I don't have a smart reply, sorry. My brain is mostly asleep.

The one comment I do have to make is that if you're brute forcing like this:

for y in [0, infinity):
    if (y * y) % 269 == 66:
        return y

you might find it nicer to do this:

for n in [0, infinity):
    y = sqrt(66 + (n * 269))
    if y is an integer:
        return y

If I think of a smarter way to do it tomorrow, I'll post something.