0
$\begingroup$

I'm implementing arithmetics for elliptic curves over secp256r1 as a homework assignment.

For scalar multiplication, the assignment specifically specifies that $k$ is "any hexidecimal encoded integer" (for the multiplication $kP$).

How is multiplication defined for negative values of $k$? My best guess is that $k$ is calculated modulo #$E(\mathbb{F}_p)$, which in this case is $nh$ (the cardinality of the group of the points on the curve) as specified by SEC (in http://www.secg.org/download/aid-386/sec2_final.pdf). Is that correct?

If not, how is scalar multiplication defined for negative $k$'s?

$\endgroup$

1 Answer 1

2
$\begingroup$

I am not familiar with some of the abbreviations you use, and do not know what is better in your case, but:

a. for any commutative group $(G,+)$ one has $kP = (-k) (-P)$, k integer and $P$ in $G$. So, computing one inverse in $G$ (and one in the integers) one can reduce to scalar multiplication for positive integers. Or, in other words, one can define multiplication of $P$ by a negative $k$, as multplication of $-P$ by $|k|$. [Actually, the 'commutative' is irrelevant here.]

b. in case $G$ is finite, there is also the option you mentioned, as $kP = mP$ if $k$ and $m$ are congruent modulo the cardinality of the group (the cardinality of the group, could be replaced by the exponent of the group, or if you just want it for a specific $P$ by the order of this element $P$.)

ps: I know that in general 'homework' is not answered on this site, but this seems to be an atypical case to me, and thus I thought an exception might be justified. (If I misjudged this, feel free to delete, or ask me to delete.)

$\endgroup$
2
  • $\begingroup$ Thank you! The option a) was new to me and certainly interesting. As this is only a small part of a homework, I thought it to be ok to ask about it. I'm not asking for an implementation, just a definition which I have been unable to find despite reading several books and papers about it. Thank you again! $\endgroup$
    – Jonas WS
    Mar 17, 2011 at 14:15
  • $\begingroup$ Regarding the second part of your comment: Yes, this was my reasoning. And, thus of course, I agree, it was alright to ask (else I would not have answered). $\endgroup$
    – user9072
    Mar 17, 2011 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.