Solve Elliptic Curve equation

Question

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.

Answer 1

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