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