Elliptic curve arithmetic: Difference between revisions
Updated C++ entry, add subtraction fixed negative integer multiplication
m (minor c++ edit) |
(Updated C++ entry, add subtraction fixed negative integer multiplication) |
||
Line 141:
{
double m_x, m_y;
static constexpr double
static constexpr double B = 7; // the 'b' in y^2 = x^3 + a * x + b
// '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:
friend std::ostream& operator<<(std::ostream&, const EllipticPoint&);
// Create a point that is initialized to Zero
constexpr EllipticPoint() noexcept : m_x(
// Create a point based on the yCoordiante. For a curve with a = 0 and b = 7
Line 161 ⟶ 187:
bool IsZero() const noexcept
{
//
bool isNotZero = abs(m_y) < ZeroThreshold;
return !isNotZero;
}
// make a
EllipticPoint operator-() const noexcept
{
Line 193 ⟶ 217:
{
double L = (rhs.m_y - m_y) / (rhs.m_x - m_x);
if(
{
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))
Line 199 ⟶ 229:
// in this case rhs == -lhs, the result should be 0
*this = EllipticPoint();
}
else
}
}
Line 228 ⟶ 241:
}
//
EllipticPoint& operator-=(const EllipticPoint& rhs) noexcept
{
*this+= -rhs;
return *this;
}
// multiply the point by an integer (p *= 3)
EllipticPoint& operator*=(int rhs) noexcept
{
Line 234 ⟶ 254:
EllipticPoint p = *this;
if(rhs < 0)
{
// change p * -rhs to -p * rhs
rhs = -rhs;
p = -p;
}
for (int i = 1; i <= rhs; i <<= 1)
{
if (i & rhs) r += p;
p
}
Line 249 ⟶ 276:
{
lhs += rhs;
return lhs;
}
// subtract points (p - q)
inline EllipticPoint operator-(EllipticPoint lhs, const EllipticPoint& rhs) noexcept
{
lhs += -rhs;
return lhs;
}
Line 258 ⟶ 292:
return lhs;
}
// multiply by an integer (3 * p)
inline EllipticPoint operator*(const int lhs, EllipticPoint rhs) noexcept
{
rhs *= lhs;
return rhs;
}
// print the point
Line 272 ⟶ 314:
cout << "b = " << b;
const EllipticPoint c = a + b;
cout << "c = a + b = " << c;
cout << "a + b
cout << "a + b - (b + a) = " << a + b - (b + a) << "\n";
cout << "
cout << "a
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;
EllipticPoint g;
cout << "g = zero = " << g;
cout << "g += a = " << (g+=a);
cout << "g += zero = " << (g+=zero);
cout << "g += b = " << (g+=b);
cout << "
EllipticPoint special(0); // the point where
cout << "special = " << special; // this has the minimum possible value for x
cout << "special *= 2 = " << (special*=2); // doubling it gives zero
return 0;
Line 301 ⟶ 345:
b = (-1.44225, 2)
c = a + b = (10.3754, -33.5245)
a + b
a +
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 += a = (-1.81712, 1)
g += zero = (-1.81712, 1)
g += b = (10.3754, -33.5245)
b + b - b * 2 = (Zero)
special = (-1.91293, 0)
special *= 2 = (Zero)
</pre>
| |||