2
$\begingroup$

Suppose you have an elliptic curve $E_{p}$: $y^{2} = x^{3} + Ax + B \mod p$ and points $P$ and $Q$ which lie on $E_{p}$.

Does there always exist $n$ such that $nP=Q$? If so, how do we solve for it? Not sure how to proceed.

$\endgroup$
  • $\begingroup$ Why would such an $n$ exist in general? $\endgroup$ – Álvaro Lozano-Robledo Jun 9 '16 at 2:24
  • $\begingroup$ good question? I guess I should have mentioned does it exist first. I will edit. $\endgroup$ – Jack Jun 9 '16 at 2:47
  • $\begingroup$ Hint: What if $P = O$? $\endgroup$ – Brandon Carter Jun 9 '16 at 14:17
2
$\begingroup$

No, such $n$ does not exist in general. Take for instance $E: y^2=x^3+x+2$ defined over $\mathbb{F}_5$. Then, $E(\mathbb{F}_5)$ has four points $$(0 : 1 : 0), (1 : 2 : 1), (1 : 3 : 1), (4 : 0 : 1)$$ and the group $E(\mathbb{F}_5)$ is cyclic of order $4$. Now take $Q=(1:2:1)$, which is a point of order $4$, and $P=2Q=(4 : 0 : 1)$. Then, there is no $n$ such that $nP=Q$, because the order of $P$ is $2$ and the order of $Q$ is $4$, so such a number $n$ cannot exist.

You might say "well, but in your example $2Q=P$, so there is such $n$ if we reverse the role of $P$ and $Q$", but then I would reply "OK, then try the same $E$ defined over $\mathbb{F}_{13}$ and you can find a point $P$ of order $4$ and a point $Q$ of order $3$ such that $nP=Q$ or $nQ=P$ is impossible either way!".

$\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.