1
$\begingroup$

I'm learning the multiplication operation on EC. From most material I can found, the multiplication $nP$ is just:

$$nP=P+P+\cdots +P+P$$ For negative factor, i.e. $(-n)P$, by above definition and the definition of $-P$, we can write $(-n)P$ as:

$$(-n)P = (-P) + (-P) + \cdots (-P)$$

My question is: is it possible to expression $(-n)P$ as $mP$ where $m>0$ under reasonable assumption? For example, we can assume the knowledge of the group order.

I'm asking so because $nP$ on EC is analogous to exponentiation in group $\mathbb{G}$ with order $p$. And in the latter case we have $g^{-n} \equiv g ^{k\phi(q)-n}\pmod q, \forall k\in \mathbb{Z}$ by Fermat's little. So I'm wondering if there is a similar result for EC.

$\endgroup$
3
$\begingroup$

If you know the order of the curve (we'll call it $q$), then it's easy.

In that case, we have the identity $xP = (x + q)P$ for any $x$. Using that identity, we can express $(-n)P$ as $(q - n)P$; by the above identity, these are the same. If $q > n$, this gives you your answer.

The more general answer (which works for any $n$) is $(-n \bmod q)P$, using the convention that $a \bmod b$ is that integer which is between 0 and $b-1$, and which is congruent to $a$ modulo $b$.

This is exactly analogous to the $\mathbb{G}^*$ case; in that case, the size of the group is $\phi(q)$; in this Elliptic curve case, the size of the group is $q$.

| improve this answer | |
$\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.