Method: Integer#invmod

Defined in:
lib/crypto_toolchain/extensions/integer_extensions.rb

#invmod(n) ⇒ Object Also known as: mod_inverse, modinv

From Wikipedia: en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode

Raises:

  • (ArgumentError) 


31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/crypto_toolchain/extensions/integer_extensions.rb', line 31

def invmod(n)
  a = self
  t = 0
  new_t = 1
  r = n
  new_r = a
  while new_r != 0
      quotient = r / new_r
      t, new_t = new_t, (t - quotient * new_t)
      r, new_r = new_r, (r - quotient * new_r)
  end
  raise ArgumentError.new("#{self} is not invertible") if r > 1
  t += n if t < 0
  t
end