# Solve Elliptic Curve equation

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.

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

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!".