# X9.62 Multiplying an elliptic curve point by a number

I'm currently trying to implement ecdsa and the first problem i met --
multiply an elliptic curve point by a number.

As far as i understand X9.62 gives some recommendation for doing it but i haven't managed to find anything.
It would be great to see some program like algorithm.

P.S.
Any help is appreciated. Sorry for my English and thanks.

-
Once you can add two points, multiplication by a number follows. The simplest algorithm to multiply by n>0 uses n-1 additions, much like 3*19 is 19+19+19. This can be made O(Log(n)) by methods analog to these for exponentiation. –  fgrieu Apr 13 '12 at 5:13
Sorry, NISTs-192..521 with exp. multiplying algorithm sounds not much promising; –  ted Apr 13 '12 at 5:30
I think you need to understand the idea about groups, and that "exponentiation" (when the group operation is called multiplication) and "multiplication by number" (when the group operation is called addition - as is the case for Elliptic Curve groups) are actually exactly the same thing. –  MartinSuecia Apr 13 '12 at 8:15

Well, you understand that Elliptic Curves define an operation on points we denote as +; that is, if $A$ and $B$ are two (not necessarily distinct) points, then $A+B$ is a third point (which will be distinct unless either $A$ or $B$ are the 'point-at-infinity'). If $A$ and $B$ are the same, the operation is usually called doubling instead of addition.

Now, by "multiplying an elliptic curve point by a number" (or point multiplication), what we mean is adding the point to itself the specified number of times. That is:

$\displaylines{kG =}{\underbrace{G + G + G + ... + G}}$

where exactly k $G$'s are added together.

Now, the naive implementation is just to perform $k-1$ point additions; however, because the integers we're multiplying by are huge, this is not practical.

However, point addition is associative (that is, $(A+B)+C = A+(B+C)$, that means that we can use less than $k-1$ additions; for example, to compute $8G$, we can note that:

$2G = G + G$

$4G = G + G + G + G = (G + G) + (G + G) = 2G + 2G$

$8G = 4G + 4G$

and hence we've computed $8G$ using only three additions.

One straight-forward (decent, but nonoptimal) method to do this (assuming, of course, that you have already implemented the Elliptic Curve addition function) is to use the binary addition method; just note that the Wiki article talks about 'multiplication', while you're doing addition; that is merely a difference in syntax.

-
An awesome answer but nothing from X9.62 about point multiplication by number. Still thank you. Cannot upvote for now. –  ted Apr 13 '12 at 5:45
Page 91 in ANSI X9.62 defines and describes a way to perform point multiplication (they call it scalar multiplication). This is slightly different from ponchos method, choose whichever one you want. –  MartinSuecia Apr 13 '12 at 8:03