Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Given the elliptic curve

$$E:y^2 = x^3+17x+5 \mod 59$$

with point $P = (4,14)$, how do I find $x$ such that compute $x\cdot P = (11,44)$

Is there a mathematical method to compute $x$, or do I simply compute a lot of $x$'s and hope for the best?

If it helps, I know $8P = (16,40)$

share|improve this question

2 Answers 2

As mentioned by Thekwasti, what you want here is compute a discrete logarithm, but while it is true that in general computing discrete logarithms is "hard" (which is why they are used in cryptography), in your case the group is small enough to make even a brute force search completely feasible. So the goal of the exercise is probably to make you implement at least one of the following algorithms:

  • Brute force search
  • Shanks's "baby step, giant step"
  • Pollard's rho

You will normally find that they are in increasing order of efficiency (although here the group is so small that the difference might not be noticeable).

share|improve this answer

I am not sure why you write $xP$ (with capital P) but I guess you just mean $x \cdot p = p + \ldots p$ ($n$-many times):

What you search for is the discrete logarithm. The fact, that finding a discrete logrithm on elliptic curves over $\mathbb F_P$ seems to be very hard, is exactly what makes them useful for cryptology. If you find a better way than just trying many $x$, do not tell anyone. The NSA will come and get you :)

share|improve this answer
    
Some folks write curve points with uppercase letters. –  Reid Mar 9 at 17:35
    
Yes i know, but he had switch between lower und upper case letters. Now the question has been edited and is consistently written with upper case letters. –  Thekwasti Mar 9 at 17:56
    
I just tried to neaten it up - whether upper or lower is correct, the only certainty was that the mixture of both was an error. –  figlesquidge Mar 10 at 19:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.