5
$\begingroup$

Let $E$ be an elliptic curve over a finite field $F_p$. Given $n$ be a positive integer and $Q$ be a point on $E$, assume that $Q=nP$, how can we find this $P$? We can assume that $n|p-1$. If $n$ is "small", I would imagine that it is possible using division polynomials. Is it a difficult problem if $n$ is large enough? How difficult is it?

$\endgroup$
  • 3
    $\begingroup$ You can recover $P$ by computing $(n^{-1} \bmod l)\cdot Q$, where $l$ is the order of $Q$. $\endgroup$ – Samuel Neves Jun 29 '13 at 2:57
  • $\begingroup$ Solving $Q=np$ for $n$ is the discrete logarithm problem and expensive. Solving for $P$ is cheap (assuming the order of the curve is known). $\endgroup$ – CodesInChaos Jun 29 '13 at 11:20
  • $\begingroup$ Why do you assume that $n$ divides $p-1$ ? Is there any specific reason for this condition, if so could you explain what it is ? $\endgroup$ – minar Jul 14 '13 at 17:56
8
$\begingroup$

As Samuel Neves described in the comments it is trivially possible to obtain $P$ from $Q=nP$, given $Q$ and the integer $n$.

Simply compute $k=n^{-1} \bmod l$, with $l=|E(\mathbb F_p)|$ being the order (=the number of points) of the curve. $l$ is usually known.

Then, to obtain the desired point $P$, calculate $P=kQ=knP$ and you're done.

$\endgroup$

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.