Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# smac89/egcd.py

Last active Feb 18, 2021
Extended Euclidean Algorithm in Python (Without recurrsion)
 #!/usr/bin/python3 import math # Taken in part from: https://www.geeksforgeeks.org/python-program-for-basic-and-extended-euclidean-algorithms-2/ def gcdExtended(a, b): """ Calculates the GCD of the two given numbers, as well as the coefficients x and y such that ax + by = gcd(a,b). This is useful in cryptography See: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm Parameters: a (int): The first number b (int): The second number Returns: (int, int, int): The GCD, x, y """ stack =  * 5 * int(1 + math.log10(min(a, b))) ptr = 0 while a != 0: ptr -= 1 stack[ptr] = b // a a, b = b % a, a gcd = b x, y = 0, 1 while ptr != 0: x, y = y - stack[ptr] * x, x ptr += 1 return gcd, x, y if __name__ == '__main__': import sys if len(sys.argv[1:]) == 2: print (gcdExtended(int(sys.argv), int(sys.argv))) else: for line in sys.stdin: print (gcdExtended(*map(int, line.split())))
to join this conversation on GitHub. Already have an account? Sign in to comment