Class: Integer

Inherits:
Numeric show all
Defined in:
lib/numeric_inverse/ext/integer.rb,
lib/numeric_inverse/ext/integer.rb

Instance Method Summary collapse

Instance Method Details

#inverse ⇒ Rational #inverse(m) ⇒ Integer Also known as: inv

Returns its inverse.

Examples:

63.inv        #=> (1/63)
63.inv * 63   #=> (1/1)

63.inv(100)              #=> 27
63.inv(100) * 63         #=> 1701
63.inv(100) * 63 % 100   #=> 1

64.inv(100)   #=> ArgumentError: modulus 100 is not coprime to 64

Overloads:

  • #inverse ⇒ Rational

    Returns inverse.

    Returns:

    • (Rational) —

      inverse

  • #inverse(m) ⇒ Integer

    Returns modular multiplicative inverse.

    Parameters:

    Returns:

    • (Integer) —

      modular multiplicative inverse

    Raises:

    • (ArgumentError) —

      if m is not coprime to self



25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/numeric_inverse/ext/integer.rb', line 25

def inverse(m = nil)
  return Rational(1, self) if m.nil?

  # extended Euclidean algorithm
  a, b, x, x0 = self, m, 1, 0
  until b.zero?
    a, (q, b) = b, a.divmod(b)
    x, x0 = x0, x - q * x0
  end

  # x is an inverse iff self.gcd(m) == 1
  if a.abs != 1
    raise ArgumentError,
          "modulus #{m} is not coprime to #{self}"
  end

  x = -x if a < 0
  x % m.abs   # 0 <= x < |m|
end