class EllipticCurve::EC
The base class which holds an elliptic curve
Attributes
a[R]
b[R]
p[R]
Public Class Methods
new(a, b, p)
click to toggle source
y^2 = x^3 + ax + b p: modulo
# File lib/elliptic_curve.rb, line 14 def initialize(a, b, p) @a, @b, @p = a, b, p end
Public Instance Methods
add(p1, p2)
click to toggle source
Adds two points together - searches the third point on a line between the two points
# File lib/elliptic_curve.rb, line 41 def add(p1, p2) if p2.is_infinity? return p1 elsif p1.is_infinity? return p2 elsif p1.x == p2.x if p1.y == -p2.y return P.new(ec, Float::INFINITY, Float::INFINITY) else k = (3 * p1.x**2+@a) * get_inv_p(2 * p1.y) x = (k**2 - 2 * p1.x) % @p return P.new(self, x, (k*(p1.x-x)-p1.y) % @p) end else k = (p2.y-p1.y) * get_inv_p(p2.x-p1.x) x = (k**2-p1.x-p2.x) % @p return P.new(self, x, (k * (p1.x-x)-p1.y) % @p) end end
get_inv_p(s)
click to toggle source
gets the inverse modulo p Copied from en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers
# File lib/elliptic_curve.rb, line 20 def get_inv_p(s) s < 0 and return get_inv_p(s % @p) t, newt = 0, 1 r, newr = @p, s while newr != 0 do quotient = (r / newr).floor t, newt = newt, t - quotient * newt r, newr = newr, r - quotient * newr end if r > 1 then raise "#{s} is not invertible" end if t < 0 then return t + @p else return t end end