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.

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

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.