module CryptoGost::ModularArithmetic

ModularArithmetic

Take this code from here: gist.github.com/jingoro/2388745 @author jingoro

Public Instance Methods

gcd(x, y) click to toggle source
# File lib/crypto_gost/modular_arithmetic.rb, line 10
def gcd(x, y)
  gcdext(x, y).first
end
gcdext(x, y) click to toggle source
# File lib/crypto_gost/modular_arithmetic.rb, line 14
def gcdext(x, y)
  if x < 0
    g, a, b = gcdext(-x, y)
    return [g, -a, b]
  end
  if y < 0
    g, a, b = gcdext(x, -y)
    return [g, a, -b]
  end
  r0, r1 = x, y
  a0 = b1 = 1
  a1 = b0 = 0
  until r1.zero?
    q = r0 / r1
    r0, r1 = r1, r0 - q*r1
    a0, a1 = a1, a0 - q*a1
    b0, b1 = b1, b0 - q*b1
  end
  [r0, a0, b0]
end
invert(num, mod) click to toggle source
# File lib/crypto_gost/modular_arithmetic.rb, line 35
def invert(num, mod)
  g, a, b = gcdext(num, mod)
  unless g == 1
    raise ZeroDivisionError.new("#{num} has no inverse modulo #{mod}")
  end
  a % mod
end