Point multiplication in Elliptic Curves

I was browsing the web for information about the binary multiplication (also known as "left-to-right multiplication") in Ellipti curves. I wrote a demonstration of the algorithm. Unfortunately, it's very brief version, but it might be interesting for someone :) This demonstration generates the right point multiplication sequency in binary multiplication of point. First - very short theory. Point multiplication is the operation: Q = k∙P. Point multiplication is the combination of point doubling and point addition. The number k is converted into binary form and according to it’s value (0 or 1) the addition is performed or not. The simplest and the oldest is the binary multiplication method (also called “left to right point multiplication”). The algorithm:

Ø Input: A point P and l-bit integer k, where k = (k[l - 1]...k[1]k[0]), k[i] = {0, 1};

Ø Output: k∙P.

Ø Q = 0

Ø For j = l – 1 to 0 do

o Q = [2]Q

o If k_j = 1, then Q = Q + P

Ø Return Q

So, we need to get the binary representation of our k. It can be done with & operator in C. The addition must be performed, if k[i] = 1 (condition: number & 1). So, the demonstration code looks like that:

void sim_bmul(const long number) { long no = number; string line; int p[sizeof(long) * 8]; /* Get binary digits */ int i = 0; while(no > 0) { if (no & 1) p[i++] = 1; else (p[i++] = 0); no >>= 1; } i--; while(i >= 0) { /* Doubling emulation */ if (line.size() != 0) line = line.insert(0, "(2"); /* End of doubling emulation */ if (p[i] == 1) { /* Addition simulation */ if (line.size() == 0) line.insert(line.size(), "(P"); else line.insert(line.size(), " + P"); } if (line.size() > 0) line.insert(line.size(), ")"); cout << line.c_str() << endl; i--; } cout << line.c_str() << endl; }

So, if we pass 11 (in binary: 1011) this demonstration should give us the following sentence: (2(2(2(P)) + P) + P). Doubling emulation looks quite weird, but at the moment I could find a better solution. Well, next time... Nice ;)