Extended GCD (Extended Euclid Algorithm)

This is the extended Euclid algorithm.  This is useful for finding the multiplicative inverse (i.e., find d such that for a given e, d*e mod m = 1) of a number in a modulus space (integers between 0 and the modulus m).  This is commonly used in the RSA algorithm to determine the decryption exponent from the encryption exponent.


def extended_gcd(b,m,_recursion_depth=0)
  if b % m == 0
    temp = [0,1]
    return temp
  else
    temp = extended_gcd(m, b % m, _recursion_depth+1)
    temp2 = [temp[1], temp[0]-temp[1] * ((b/m).to_i)]
    if _recursion_depth == 0
      return temp2[0] % m
    else
      return temp2
    end
  end
end