Elliptic Curve

curve.rb

require 'prime'

class Point
  attr_accessor :x, :y

  def initialize(x, y)
    @x = x.to_i
    @y = y.to_i
  end

  def infinity?
    @x == -1 && @y == -1
  end

  def self.infinity
    Point.new(-1, -1)
  end

  def clone
    Point.new(@x, @y)
  end

  def ==(other)
    @x == other.x && @y == other.y
  end

  def to_s
    "(#{@x}, #{@y})"
  end
end

class FiniteNumber
  def initialize(v, mod)
    @v = v.to_i % mod
    @mod = mod
  end

  def to_i
    @v
  end

  def to_s
    @v.to_s
  end

  def ==(other)
    @v.to_i == other.to_i
  end

  def /(denom)
    return nil if (denom.to_i % @mod) == 0
    FiniteNumber.new(denom, @mod).inverse * @v
  end

  def +(addend)
    FiniteNumber.new(@v + addend.to_i, @mod)
  end

  def -(sub)
    FiniteNumber.new(@v - sub.to_i, @mod)
  end

  def *(mul)
    FiniteNumber.new(@v * mul.to_i, @mod)
  end

  def **(exp)
    FiniteNumber.new(@v ** exp.to_i, @mod)
  end

  def sqrt
    (0...@mod).select { |rt| rt ** 2 % @mod == @v}.map do |rt|
      FiniteNumber.new(rt, @mod)
    end
  end

  def inverse
    return nil if @v == 0
    FiniteNumber.new(@v ** (@mod - 2), @mod)
  end
end

class FiniteCurve
  def initialize(a, b, mod)
    @a = a
    @b = b
    @mod = mod
  end

  def num(v)
    FiniteNumber.new(v, @mod)
  end

  def points
    points = []
    (0...@mod).map{|x| num(x)}.each do |x|
      ysquared = x ** 3 + x * @a + @b
      ysquared.sqrt.each do |y|
        points << Point.new(x, y)
      end
    end
    points
  end

  def order(point)
    i = 1
    until (scalar_mult(i, point)).infinity?
      i += 1
      return nil if i > 10000
    end
    return i
  end

  def orders
    sets = []
    points.each do |pt|
      ord = order(pt)
      sets << (1...ord).map {|m| scalar_mult(m, pt)}
    end
    sets
  end

  def max_order_point
    max = 0
    maxpoint = nil
    points.each do |pt|
      ord = order(pt)
      if ord > max and Prime.prime?(ord)
        max = ord
        maxpoint = pt
      end
    end
    return {max: max, point: maxpoint}
  end

  def add(p, q)
    return q.clone if p.infinity?
    return p.clone if q.infinity?

    c = (num(q.y) - p.y) / (num(q.x) - p.x)
    return Point.infinity if c.nil?
    x = c ** 2 - p.x - q.x
    y = c * (num(p.x) - x) - p.y

    Point.new(x, y)
  end

  def double(p)
    c = (num(p.x) ** 2 * 3 + @a) / (num(p.y) * 2)
    return Point.infinity if c.nil?
    x = c ** 2 - 2 * p.x
    y = c * (num(p.x) - x) - p.y

    Point.new(x, y)
  end

  def scalar_mult(num, point)
    return Point.infinity if num == 0
    if num % 2 == 1
      return add(point, scalar_mult(num - 1, point))
    else
      return scalar_mult(num / 2, double(point))
    end
  end
end

(29..67).each do |mod|
  next unless Prime.prime?(mod)
  curve = FiniteCurve.new(0, 7, mod)
  p mod
  p curve.max_order_point
end