# Binary multiplication on elliptic curves in C++

I wrote a function in C++ which uses binary multiplication (a form of binary exponentation):

public: Point mul(Point p, unsigned int n)
{
// actually these Points shouldn't have negative coordinates, I use Point(-1, -1) as neutral element on addition (like 0)
Point r = Point(-1, -1);
n = mod(n, m);  // the %-operator doesn't return a non-negative integer in every case so I wrote a function
unsigned int mask = 1 << (sizeof (n) - 1);  // more flexible and platform independent than 1 << 31
{
r = add(r, r);
if (mask & n)
r = add(r, p);
}
return r;
}


Notes:

• The function calculates points on elliptic curves over a finite field GF(m)
• Point is a class I wrote for this. It doesn't do much beside holding two coordinates x and y
• I just wondered if there is an easier / cleaner solution for binary multiplcation in C++ than I implemented
• The algorithm is like 'double and add' instead of 'square and multiply'

EDITS:

This is my Point class:

class Point
{
public:
long long int x, y;

public: Point(long long int _x, long long int _y)
{
x = _x;
y = _y;
}

public: void print()
{
cout << "(";
cout << x;
cout << ", ";
cout << y;
cout ")";
}
};


The mul function is part of the class EllipticCurve:

class EllipticCurve
{
public:
int a;
int b;
unsigned int m;

public: EllipticCurve(int _a, int_b, unsigned int modul)
{
a = _a;
b = _b;
m = modul;
}

public: Point generate(unsigned long long int x)
{
// looks for Points on the curve with the given x coordinate
// returns the first matching point
}

public: Point add(Point p, Point q)
{
// complex addition function with if-else trees
// the function code is not needed for this question
}

public: Point mul(Point p, unsigned int n)
{
// see above
}
};


Please remember that this question is about the mul function, not the rest of the code. I inserted it only for a better understanding.

• @TobySpeight sorry, that wasmy mistake. Of course I used C++ for this – Aemyl May 18 '17 at 12:03

    n = mod(n, m);  // the %-operator doesn't return a non-negative integer in every case so I wrote a function


I would find a comment explaining m more useful than a comment explaining why you made a mod function, because everyone ends up writing a mod function which behaves sensibly.

I don't know much about elliptic curves, but I have worked with finite fields. Are you sure it makes sense to take n mod m as though they were integers? The only makes sense to me if m is also the characteristic (i.e. if it's a field of prime order).

    unsigned int mask = 1 << (sizeof (n) - 1);  // more flexible and platform independent than 1 << 31


Why loop down? If you loop up then you get the platform-independence for free, and also you loop fewer times when n is small. Obviously the loop invariant would change, but it would be closer to school long multiplication and so might also be more maintainable.

    for (; n; n >>= 1)
{
if (n & 1)
r = add(r, p);
p = add(p, p);
}

• thanks for the response. yes, it is a field of prime order, m is prime. And I'm not sure about if looping up still gives the correct results - I mean that would calculate e.g. p * 0b110101 instead of p * 0b101011 if you read the binary digits from rigth to left instead of left to right. wouldn't it? – Aemyl May 18 '17 at 12:14
• and you're right, the use of mod() isn't necessary anoymore since I use unsigned int. I still need this function in other code parts though. – Aemyl May 18 '17 at 12:30
• @Aemyl, if you change the direction of the loop you'll have to change the body as well, but the result will be very similar to the way you do long multiplication. – Peter Taylor May 18 '17 at 12:48
• Oh, OK. That seems logic. However, I have no idea how to change the body correctly :/ – Aemyl May 18 '17 at 13:09

Just a one liner. The field public: and its counterparts define a section. So everything after public: is public until protected/private come up. So there is no need to put it before every function.

### Bug in mask

Your function doesn't actually do the right thing because of this line:

unsigned int mask = 1 << (sizeof (n) - 1);


On a 32-bit system, you wanted mask to be 1 << 31 but what you actually got was 1 << 3 because sizeof(unsigned int) is 4. The correct way would be:

unsigned int mask = 1 << (sizeof(n) * CHAR_BIT - 1);


because sizeof returns a number of bytes and CHAR_BIT is defined to be the number of bits per byte.

Of course, if you used the loop Peter Taylor suggested, you wouldn't even need mask.

• you're right, I forgot that sizeof returns the bytesize instead of the bitsize. Thanks a lot! – Aemyl May 19 '17 at 5:51