module NumberTheory::Utils

Public Class Methods

_eca(a, b) click to toggle source

helper function for mod_inv

# File lib/number-theory/utils.rb, line 56
def self._eca(a, b)
  return b, 0, 1 if a == 0
  g, y, x = self._eca(b % a, a)
  return g, x - y * (b / a).floor, y
end
mod_exp(a, b, m) click to toggle source

Returns a^b (mod m). Negative exponents are allowed.

Example

>> Utils.mod_exp(12, 34, 107)
=> 61

Algorithm

# File lib/number-theory/utils.rb, line 22
def self.mod_exp(a, b, m)
  if b >= 0
    res = 1
    while b > 0
      res = (res * a) % m if b & 1 != 0
      b >>= 1
      a = (a * a) % m
    end
    res
  else
    self.mod_exp(self.mod_inv(a, m), -b, m)
  end
end
mod_inv(a, m) click to toggle source

Returns the modular inverse of a, i.e. the number b such that a * b = 1 (mod m)

Example

>> Utils.mod_inv(121, 107)
=> 23

Algorithm

# File lib/number-theory/utils.rb, line 49
def self.mod_inv(a, m)
  return 0 if a % m == 0
  g, a, y = self._eca(a, m) 
  return g != 1 ? 0 : a % m
end