1
$\begingroup$

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)$

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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 :)

$\endgroup$
3
  • $\begingroup$ Some folks write curve points with uppercase letters. $\endgroup$
    – Reid
    Mar 9 '14 at 17:35
  • $\begingroup$ 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. $\endgroup$
    – Thekwasti
    Mar 9 '14 at 17:56
  • $\begingroup$ 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. $\endgroup$ Mar 10 '14 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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