Elliptic curve arithmetic: Difference between revisions

Content added Content deleted
m (minor c++ edit)
(Updated C++ entry, add subtraction fixed negative integer multiplication)
Line 141: Line 141:
{
{
double m_x, m_y;
double m_x, m_y;
static constexpr double MagicZeroMarker = -99.0;
static constexpr double ZeroThreshold = 1e20;
static constexpr double B = 7; // the 'b' in y^2 = x^3 + a * x + b
static constexpr double B = 7; // the 'b' in y^2 = x^3 + a * x + b
// 'a' is 0
// 'a' is 0
void Double() noexcept
{
if(IsZero())
{
// doubling zero is still zero
return;
}
// based on the property of the curve, the line going through the
// current point and the negative doubled point is tangent to the
// curve at the current point. wikipedia has a nice diagram.
if(m_y == 0)
{
// at this point the tangent to the curve is vertical.
// this point doubled is 0
*this = EllipticPoint();
}
else
{
double L = (3 * m_x * m_x) / (2 * m_y);
double newX = L * L - 2 * m_x;
m_y = L * (m_x - newX) - m_y;
m_x = newX;
}
}
public:
public:
friend std::ostream& operator<<(std::ostream&, const EllipticPoint&);
friend std::ostream& operator<<(std::ostream&, const EllipticPoint&);


// Create a point that is initialized to Zero
// Create a point that is initialized to Zero
constexpr EllipticPoint() noexcept : m_x(MagicZeroMarker - 1), m_y(0) {}
constexpr EllipticPoint() noexcept : m_x(0), m_y(ZeroThreshold * 1.01) {}


// Create a point based on the yCoordiante. For a curve with a = 0 and b = 7
// Create a point based on the yCoordiante. For a curve with a = 0 and b = 7
Line 161: Line 187:
bool IsZero() const noexcept
bool IsZero() const noexcept
{
{
// x and y are undefined at the Zero point. Internally
// when the elliptic point is at 0, y = +/- infinity
bool isNotZero = abs(m_y) < ZeroThreshold;
// represent Zero with a large negative x. Such points
return !isNotZero;
// cannot be on the curve itself.
bool isZero = m_x <= MagicZeroMarker;
return isZero;
}
}


// make a negaive version of the point ( p = -q)
// make a negative version of the point (p = -q)
EllipticPoint operator-() const noexcept
EllipticPoint operator-() const noexcept
{
{
Line 193: Line 217:
{
{
double L = (rhs.m_y - m_y) / (rhs.m_x - m_x);
double L = (rhs.m_y - m_y) / (rhs.m_x - m_x);
if(!isfinite(L))
if(isfinite(L))
{
double newX = L * L - m_x - rhs.m_x;
m_y = L * (m_x - newX) - m_y;
m_x = newX;
}
else
{
{
if(signbit(m_y) != signbit(rhs.m_y))
if(signbit(m_y) != signbit(rhs.m_y))
Line 199: Line 229:
// in this case rhs == -lhs, the result should be 0
// in this case rhs == -lhs, the result should be 0
*this = EllipticPoint();
*this = EllipticPoint();
return *this;
}
}
else

// in this case rhs == lhs. based on the property
{
// of the curve, lhs + rhs + the new value must = 0.
// in this case rhs == lhs.
// the line going through all three points is tangent to
Double();
// curve at rhs (and lhs). wikipedia has a nice diagram.
}
// the math used to calculate L is different.
L = (3 * m_x * m_x) / (2 * m_y);
}
}
double newX = L * L - m_x - rhs.m_x;
double newY = L * (m_x - newX) - m_y;
if (abs(newY) > 1e20)
{
// snap this point to zero
*this = EllipticPoint();
}
else
{
m_x = newX;
m_y = newY;
}
}
}


Line 228: Line 241:
}
}


// multiply the point by an integer ( p *= 3)
// subtract a point from this one (p -= q)
EllipticPoint& operator-=(const EllipticPoint& rhs) noexcept
{
*this+= -rhs;
return *this;
}
// multiply the point by an integer (p *= 3)
EllipticPoint& operator*=(int rhs) noexcept
EllipticPoint& operator*=(int rhs) noexcept
{
{
Line 234: Line 254:
EllipticPoint p = *this;
EllipticPoint p = *this;


if(rhs < 0)
{
// change p * -rhs to -p * rhs
rhs = -rhs;
p = -p;
}
for (int i = 1; i <= rhs; i <<= 1)
for (int i = 1; i <= rhs; i <<= 1)
{
{
if (i & rhs) r += p;
if (i & rhs) r += p;
p += p;
p.Double();
}
}


Line 249: Line 276:
{
{
lhs += rhs;
lhs += rhs;
return lhs;
}

// subtract points (p - q)
inline EllipticPoint operator-(EllipticPoint lhs, const EllipticPoint& rhs) noexcept
{
lhs += -rhs;
return lhs;
return lhs;
}
}
Line 258: Line 292:
return lhs;
return lhs;
}
}

// multiply by an integer (3 * p)
inline EllipticPoint operator*(const int lhs, EllipticPoint rhs) noexcept
{
rhs *= lhs;
return rhs;
}



// print the point
// print the point
Line 272: Line 314:
cout << "b = " << b;
cout << "b = " << b;
const EllipticPoint c = a + b;
const EllipticPoint c = a + b;
cout << "c = a + b = " << c;
cout << "c = a + b = " << c;
cout << "a + b + c = " << a + b + c;
cout << "a + b - c = " << a + b - c;
cout << "a + b - (b + a) = " << a + b - (b + a) << "\n";
const EllipticPoint d = -c;

cout << "d = -c = " << d;
cout << "c + d = " << c + d;
cout << "a + a + a + a + a - 5 * a = " << a + a + a + a + a - 5 * a;
cout << "a + (b + d) = " << a + (b + d);
cout << "a * 12345 = " << a * 12345;
cout << "a * 12345 = " << a * 12345 << "\n";
cout << "a * -12345 = " << a * -12345;
cout << "a * 12345 + a * -12345 = " << a * 12345 + a * -12345;
cout << "a * 12345 - (a * 12000 + a * 345) = " << a * 12345 - (a * 12000 + a * 345);
cout << "a * 12345 - (a * 12001 + a * 345) = " << a * 12345 - (a * 12000 + a * 344) << "\n";


const EllipticPoint zero;
const EllipticPoint zero;
EllipticPoint g;
EllipticPoint g;
cout << "g = zero = " << g;
cout << "g = zero = " << g;
cout << "g+=a = " << (g+=a);
cout << "g += a = " << (g+=a);
cout << "g+=zero = " << (g+=zero);
cout << "g += zero = " << (g+=zero);
cout << "g+=b = " << (g+=b);
cout << "g += b = " << (g+=b);
cout << "g*=2 = " << (g*=2) << "\n";
cout << "b + b - b * 2 = " << (b + b - b * 2) << "\n";


EllipticPoint special(0); // the point where it crosses the x-axis
EllipticPoint special(0); // the point where the curve crosses the x-axis
cout << "special = " << special; // this has the minimum possible value for x
cout << "special = " << special; // this has the minimum possible value for x
cout << "special*=2 = " << (special*=2); // doubling it gives zero. at this point
cout << "special *= 2 = " << (special*=2); // doubling it gives zero
// the tangent to the curve is vertical
return 0;
return 0;
Line 301: Line 345:
b = (-1.44225, 2)
b = (-1.44225, 2)
c = a + b = (10.3754, -33.5245)
c = a + b = (10.3754, -33.5245)
a + b + c = (2.44845, -4.65598)
a + b - c = (Zero)
d = -c = (10.3754, 33.5245)
a + b - (b + a) = (Zero)

c + d = (Zero)
a + (b + d) = (Zero)
a + a + a + a + a - 5 * a = (Zero)
a * 12345 = (10.7586, 35.3874)
a * 12345 = (10.7586, 35.3874)
a * -12345 = (10.7586, -35.3874)
a * 12345 + a * -12345 = (Zero)
a * 12345 - (a * 12000 + a * 345) = (Zero)
a * 12345 - (a * 12001 + a * 345) = (-1.81712, 1)


g = zero = (Zero)
g = zero = (Zero)
g+=a = (-1.81712, 1)
g += a = (-1.81712, 1)
g+=zero = (-1.81712, 1)
g += zero = (-1.81712, 1)
g+=b = (10.3754, -33.5245)
g += b = (10.3754, -33.5245)
b + b - b * 2 = (Zero)
g*=2 = (2.44845, -4.65598)


special = (-1.91293, 0)
special = (-1.91293, 0)
special*=2 = (Zero)
special *= 2 = (Zero)
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Elliptic_curve_arithmetic"