Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
You can recover $P$ by computing $(n^{-1} \bmod l)\cdot Q$, where $l$ is the order of $Q$. – Samuel Neves Jun 29 '13 at 2:57
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). – CodesInChaos Jun 29 '13 at 11:20
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 ? – minar Jul 14 '13 at 17:56

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

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.

share|improve this answer

Your Answer


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.