Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.)

share|improve this answer
    
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! –  Jonas WS Mar 17 '11 at 14:15
    
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). –  quid Mar 17 '11 at 14:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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