3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @TobySpeight sorry, that wasmy mistake. Of course I used C++ for this \$\endgroup\$ – Aemyl May 18 '17 at 12:03
4
\$\begingroup\$
    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);
    }
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Aemyl May 18 '17 at 12:14
  • \$\begingroup\$ 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. \$\endgroup\$ – Aemyl May 18 '17 at 12:30
  • \$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor May 18 '17 at 12:48
  • \$\begingroup\$ Oh, OK. That seems logic. However, I have no idea how to change the body correctly :/ \$\endgroup\$ – Aemyl May 18 '17 at 13:09
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.