0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Andrew Jan 10 at 18:52
  • $\begingroup$ @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. $\endgroup$ – poncho Jan 10 at 19:00
  • 1
    $\begingroup$ 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). $\endgroup$ – corpsfini Jan 10 at 19:48

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.