Ruby: Extended Euclidean Algorithm Function

A function for finding the modular multiplicative inverse, based on an extended version of the Euclidean algorithm.

	def EGCD(b,m,recLevel=0)
	if b % m == 0
	tmpVal = [0,1]
	return tmpVal
	else
	tmpVal = EGCD(m, b % m, recLevel+1)
	tmpVal2 = [tmpVal[1], tmpVal[0]-tmpVal[1] * ((b/m).to_i)]
	if recLevel == 0
	return tmpVal2[0] % m
	else
	return tmpVal2
	end
	end
	end

view raw euclidean.rb hosted with ❤ by GitHub