[python] Greatest Common Denominator

I am studying how to calculate RSA, and in the way the formula has something related to GCD, not only in RSA also in Affine Cipher also has a condition that gcd(a, b) = 1 when choosing a and b as keys.

So this is a code snippet after I have learned about gcd.
The formula is gcd(a, b) = gcd(b, a mod b), count until b = 0 (i.e. which means no more remainder left after divide by b) to find the gcd which is a.


# Euclidean Algorithm
# gcd(a, b) = gcd(b, a mod b)
# only interested in getting a.
# the final outcome will be gcd(a, b=0)
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Example gcd(792, 35)
# gcd(792, 35) = gcd(35, 792 mod 35) = gcd(35, 22)
# gcd(22, 35 mod 22) = gcd(22, 13)
# gcd(13, 22 mod 13) = gcd(13, 9)
# gcd(9, 13 mod 9) = gcd(9, 4)
# gcd(4, 9 mod 4) = gcd(4, 1)
# gcd(1, 4 mod 1) = gcd(1, 0)
# final result is 1, while b is 0
gcd = gcd(792, 35)
print(gcd)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s