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