Binary multiplication on elliptic curves in C++

Question

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
 for (; mask; mask >>= 1)
 {
 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.

• Aemyl: @TobySpeight sorry, that wasmy mistake. Of course I used C++ for this

Answer 1

 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
 for (; mask; mask >>= 1)

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);
 }

• Aemyl: 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: 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.
• Peter Taylor: @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.
• Aemyl: Oh, OK. That seems logic. However, I have no idea how to change the body correctly :/

Answer 2

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.

Answer 3

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.

• Aemyl: you're right, I forgot that sizeof returns the bytesize instead of the bitsize. Thanks a lot!