'''
Source: extendedeuclideanalgorithm.com
'''
import math
#Warning: can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can
def gcd_iterative(a, b):
""" Calculating the greatest common divisor
using the Euclidean Algorithm (non-recursive)
(Source: extendedeuclideanalgorithm.com/code)
"""
#Set default values for the quotient and the remainder
q = 0
r = 1
'''
In each iteration of the loop below, we
calculate the new quotient, remainder, a and b.
r decreases, so we stop when r = 0
'''
while(r > 0):
#The calculations
q = math.floor(a/b)
r = a - q * b
#The values for the next iteration
a = b
b = r if (r > 0) else b
return abs(b)
#Can handle b=0
def gcd_iterative_2(a, b):
""" Calculating the greatest common divisor
using the Euclidean Algorithm (non-recursive)
(Source: extendedeuclideanalgorithm.com/code)
"""
#Set default values for the quotient and the remainder
q = 0
r = 1
'''
In each iteration of the loop below, we
calculate the new quotient, remainder, a and b.
r decreases, so we stop when r = 0
'''
while(b > 0):
#The calculations
q = math.floor(a/b)
r = a - q * b
#The values for the next iteration
a = b
b = r
return abs(a)
def gcd(a, b):
""" Calculating the greatest common divisor
using the Euclidean Algorithm (recursive)
(Source: extendedeuclideanalgorithm.com/code)
"""
if(b == 0):
return abs(a)
q = math.floor(a/b)
r = a - q * b
return abs(b) if (r == 0) else gcd(b, r)
#Warning: this version can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can.
def xgcd_iterative(a, b):
""" Calculates the gcd and Bezout coefficients,
using the Extended Euclidean Algorithm (non-recursive).
(Source: extendedeuclideanalgorithm.com/code)
"""
#Set default values for the quotient, remainder,
#s-variables and t-variables
q = 0
r = 1
s1 = 1
s2 = 0
s3 = 1
t1 = 0
t2 = 1
t3 = 0
'''
In each iteration of the loop below, we
calculate the new quotient, remainder, a, b,
and the new s-variables and t-variables.
r decreases, so we stop when r = 0
'''
while(r > 0):
#The calculations
q = math.floor(a/b)
r = a - q * b
s3 = s1 - q * s2
t3 = t1 - q * t2
'''
The values for the next iteration,
(but only if there is a next iteration)
'''
if(r > 0):
a = b
b = r
s1 = s2
s2 = s3
t1 = t2
t2 = t3
return abs(b), s2, t2
#Can handle b=0
def xgcd_iterative_2(a, b):
""" Calculates the gcd and Bezout coefficients,
using the Extended Euclidean Algorithm (non-recursive).
(Source: extendedeuclideanalgorithm.com/code)
"""
#Set default values for the quotient, remainder,
#s-variables and t-variables
q = 0
r = 1
s1 = 1
s2 = 0
s3 = 1
t1 = 0
t2 = 1
t3 = 0
'''
In each iteration of the loop below, we
calculate the new quotient, remainder, a, b,
and the new s-variables and t-variables.
r decreases, so we stop when r = 0
'''
while(b > 0):
#The calculations
q = math.floor(a/b)
r = a - q * b
s3 = s1 - q * s2
t3 = t1 - q * t2
'''
The values for the next iteration,
(but only if there is a next iteration)
'''
a = b
b = r
s1 = s2
s2 = s3
t1 = t2
t2 = t3
return abs(a), s1, t1
def xgcd(a, b, s1 = 1, s2 = 0, t1 = 0, t2 = 1):
""" Calculates the gcd and Bezout coefficients,
using the Extended Euclidean Algorithm (recursive).
(Source: extendedeuclideanalgorithm.com/code)
"""
if(b == 0):
return abs(a), 1, 0
q = math.floor(a/b)
r = a - q * b
s3 = s1 - q * s2
t3 = t1 - q * t2
#if r==0, then b will be the gcd and s2, t2 the Bezout coefficients
return (abs(b), s2, t2) if (r == 0) else xgcd(b, r, s2, s3, t2, t3)
def multinv(b, n):
"""
Calculates the multiplicative inverse of a number b mod n,
using the Extended Euclidean Algorithm. If b does not have a
multiplicative inverse mod n, then throw an exception.
(Source: extendedeuclideanalgorithm.com/code)
"""
#Get the gcd and the second Bezout coefficient (t)
#from the Extended Euclidean Algorithm. (We don't need s)
my_gcd, _, t = xgcd(n, b)
#It only has a multiplicative inverse if the gcd is 1
if(my_gcd == 1):
return t % n
else:
raise ValueError('{} has no multiplicative inverse modulo {}'.format(b, n))
def main():
#Use your own values for a and b
a = 34
b = 24
'''
Euclidean algorithm:
see the output of gcd(a, b)
'''
print('Euclidean Algorithm:')
print('The gcd of', a, 'and', b, 'is', gcd(a, b))
#-------------------------------------------------------------
'''
Extended Euclidean Algorithm:
see the output of xgcd(a,b) and Bezout coefficients
And verify that they are correct
'''
my_gcd, s, t = xgcd(a, b)
verification = abs(s*a+t*b)
print('Extended Euclidean Algorithm:')
print('The gcd of', a, 'and', b, 'is', my_gcd)
print('And the Bezout coefficients: s=', s, ' and t=', t, '.', sep='')
print('And', s, '*', a, '+', t, '*', b, '=', verification)
if(my_gcd == verification):
print('So as we expect, s*a+t*b is equal to the gcd we found.')
else:
print('Something went wrong')
#------------------------------------------------------------
b = 10
n = 15
'''
Multiplicative Inverse:
Try to compute the multiplicative inverse of b mod n.
If that succeeds, verify that it's correct.
If it doesn't succeed, show the error raised by the function.
'''
print('Multiplicative inverse:')
try:
inverse = multinv(b, n);
print('We discovered that the multiplicative inverse of',
b, 'mod', n, 'equals', inverse)
verification = (inverse * b % n == 1)
if(verification):
print('And indeed,', b, '*', inverse, 'mod', n, '= 1')
else:
print('This is not correct.')
except ValueError as error:
print(error)
#Use main() as main function when you run this script
if __name__== "__main__":
main()