ring.rb

# -*- coding: utf-8 -*-

require 'prime'

def Ring(size)
  Ring.new(size)
end

class Ring
  attr_reader :size

  def initialize(size)
    fail unless size > 0
    @size = size
  end

  def to_s
    "#<Ring{0..#{size}}:#{object_id}>"
  end

  def [](k)
    k % size
  end

  def invertable_elements
    return (1...size).to_a if Prime.prime?(size)
    (0...size).select { |x| invertable?(x) }
  end

  def generator?(g)
    generator_order(g) == size - 1
  end

  def generators
    (1...size).select { |el| generator?(el) }
  end

  def generator_order(g)
    1.upto size do |a|
      return a if self[g ** a] == 1
    end
  end

  def invertable?(x)
    x.gcd(size) == 1
  end

  def totient
    (1...size).count { |el| invertable?(el) }
  end

  alias_method :φ, :totient
  alias_method :phi, :totient

  def inverse(x)
    if x >= size
      fail "#{x} is too big for ring #{self}"
    end

    unless invertable?(x)
      fail "#{x} has no inverse in ring #{self}"
    end

    extended_gcd(x, size).first
  end
end

def extended_gcd(x, y)
  x_orig, y_orig, gcd = x, y, x.gcd(y)

  a = last_b = 0
  b = last_a = 1

  until y == 0
    q = x / y
    x, y = y, x % y
    a, last_a = (last_a - q * a), a
    b, last_b = (last_b - q * b), b
  end

  a, b = last_a, last_b

  fail unless a*x_orig + b*y_orig == gcd

  [a, b]
end