Step by Step solution about How to resolve the algorithm Modular inverse step by step in the Ruby programming language

The provided Ruby code implements mathematical functions related to modular arithmetic and extended Euclidean algorithms. Modular arithmetic involves operations performed on integers with respect to a modulus (a fixed positive integer), and the extended Euclidean algorithm efficiently finds the greatest common divisor (GCD) of two integers.

Here's a detailed explanation of each function:

1. extended_gcd:

   • This function takes two integers, a and b, and computes their greatest common divisor (GCD) using the extended Euclidean algorithm.
   • It initializes last_remainder and remainder to the absolute values of a and b, respectively.
   • It also initializes four variables, x, last_x, y, and last_y, to keep track of intermediate values during the algorithm.
   • The algorithm iterates until remainder becomes 0.
   • Inside the loop, it updates last_remainder, remainder, x, last_x, y, and last_y based on the current values and the result of dividing last_remainder by remainder.
   • Finally, it returns the GCD (last_remainder) and the value of last_x, which is a Bézout coefficient representing the multiplicative inverse of a modulo b.

2. invmod:

   • This function takes two integers, e and et, and computes the modular inverse of e modulo et using the extended Euclidean algorithm.
   • It calls extended_gcd to find the GCD and the multiplicative inverse (x).
   • It checks if the GCD is not equal to 1, which means e and et are not coprime (have a GCD greater than 1), and raises an exception in that case.
   • If the GCD is 1, it returns the modular inverse (x) modulo et.

3. modinv:

   • This function takes two integers, a and m, and computes the modular inverse of a modulo m.
   • It first checks if a and m are coprime (have a GCD of 1) and raises an exception if they are not.
   • If they are coprime, it initializes m0, inv, and x0 to m, 1, and 0, respectively.
   • It then enters a loop that iterates while a is greater than 1.
   • Inside the loop, it updates inv, a, m, inv, and x0 based on the current values and the result of dividing a by m.
   • Finally, it adjusts inv if it is negative and returns the modular inverse.

4. require 'openssl':

   • This line imports the OpenSSL library, which provides cryptographic functions in Ruby.

5. OpenSSL::BN.new(42).mod_inverse(2017).to_i:

   • This line demonstrates the use of the OpenSSL library to perform modular exponentiation.
   • It creates a new BN (Bignum) object with the value 42, computes the modular inverse of 42 modulo 2017 using the mod_inverse method, and converts the result to an integer using the to_i method.

#based on pseudo code from http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Iterative_method_2 and from translating the python implementation.
def extended_gcd(a, b)
  last_remainder, remainder = a.abs, b.abs
  x, last_x, y, last_y = 0, 1, 1, 0
  while remainder != 0
    last_remainder, (quotient, remainder) = remainder, last_remainder.divmod(remainder)
    x, last_x = last_x - quotient*x, x
    y, last_y = last_y - quotient*y, y
  end

  return last_remainder, last_x * (a < 0 ? -1 : 1)
end

def invmod(e, et)
  g, x = extended_gcd(e, et)
  if g != 1
    raise 'The maths are broken!'
  end
  x % et
end


def modinv(a, m) # compute a^-1 mod m if possible
  raise "NO INVERSE - #{a} and #{m} not coprime" unless a.gcd(m) == 1
  return m if m == 1
  m0, inv, x0 = m, 1, 0
  while a > 1
    inv -= (a / m) * x0
    a, m = m, a % m
    inv, x0 = x0, inv
  end
  inv += m0 if inv < 0
  inv
end


require 'openssl'
p OpenSSL::BN.new(42).mod_inverse(2017).to_i