Skip to content

Instantly share code, notes, and snippets.

@smac89

smac89/egcd.py

Last active Feb 18, 2021
Embed
What would you like to do?
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 = [0] * 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[1]), int(sys.argv[2])))
else:
for line in sys.stdin:
print (gcdExtended(*map(int, line.split())))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment