# Division of Point in Elliptic Curve: Getting Back Point

Let $$P=(x_p,y_p)$$ be a point on elliptic curve $$E (a, b) := y^2=x^3+ax+b$$, for an integer $$n$$, there exists a point $$Q=(x_q,y_q)=nP$$ on $$E (a, b)$$.

If $$(x_q,y_q)$$ and $$n$$ are given, what is the algorithm to find $$(x_p,y_p)$$?

If possible provide code for python.

With Elliptic Curves, we can compute the order of any point (and, in particular, the point $$nP$$; this is especially easy on the curves we actually use for ECC, because those curves typically have an order $$hq$$, for a small $$h$$ and a large prime $$q$$ (and the order of any point is a divisor of $$hq$$).
So, if $$q$$ is the order of the point $$nP$$, and if $$n$$ is relatively prime to $$q$$ (since we generally have $$q$$ prime in practice), we just compute $$n^{-1} \bmod q$$; we then have $$(n^{-1} \bmod q)nP = P$$; that is, multiplying $$nP$$ by the scalar $$n^{-1} \bmod q$$ gives us back the original point.
• I am beginner so having some trouble to understand your answer, what is $n^{-1} \bmod q$? i understand $a \equiv b \bmod q$ where $b$ is the residue, but what does $n^{-1} \bmod q$ mean? is there any existing algorithm or software where i can do that? I mean where can I find the code for Magma or sage? Jan 10 '20 at 18:52
• @Andrew: $n^{-1} \bmod q$ is that value $m$ for which $n \times m \equiv 1 \pmod q$; we typically use the Extended Euclidean Method to compute such a value. I am certain that both Magma and Sage has that built in (we quite often need to compute such things), however as I am unfamiliar with either of them, I cannot tell you the built-in to compute it. Jan 10 '20 at 19:00
• To add to @poncho's answer it can be computed (when $q$ is prime) by using Fermat's Little Theorem: $n^{q-2} \bmod q$ will give you $n^{-1}\bmod q$. In SageMath, you can use n.inverse_mod(q).