Extended GCD (Extended Euclid Algorithm)
Join the DZone community and get the full member experience.Join For Free
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, temp-temp * ((b/m).to_i)] if _recursion_depth == 0 return temp2 % m else return temp2 end end end
Opinions expressed by DZone contributors are their own.