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)
cyruslab 