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 coordinatesx
andy
- 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.