module CryptoGost::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