Module: CryptoGost::ModularArithmetic

Defined in:
lib/crypto_gost/modular_arithmetic.rb

Overview

ModularArithmetic

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

Author:

  • jingoro

Class Method Summary collapse

Class Method Details

.gcd(x, y) ⇒ Object 



10
11
12
 
# File 'lib/crypto_gost/modular_arithmetic.rb', line 10

def gcd(x, y)
  gcdext(x, y).first
end

.gcdext(x, y) ⇒ Object 



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
# 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) ⇒ Object 



35
36
37
38
39
40
41
 
# 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