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 is not coprime to the receiver

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 is not coprime to the receiver"
	end

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