Function gcd

recipes/Python/572196_RSA/recipe-572196.py:93–98

(a,b)

	return u, v, a

def gcd(a,b):
	# 2.8 times faster than egcd(a,b)[2]
	a,b=(b,a) if a<b else (a,b)
	while b:
		a,b=b,a%b
	return a

def modInverse(e,n):
	# d such that de = 1 (mod n)