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.

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
2  
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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.