35 lines
788 B
Python
35 lines
788 B
Python
#!/usr/bin/env python3
|
|
|
|
def gcd(a, b):
|
|
"""
|
|
This function calculate the GCD (Greatest Common Divisor of the number a of b
|
|
Args:
|
|
a (Integer): the number a
|
|
b (integer): the number b
|
|
|
|
Return:
|
|
the GCD
|
|
"""
|
|
|
|
if b == 0:
|
|
return a
|
|
return gcd(b, a%b)
|
|
|
|
def egcd(a, b):
|
|
"""
|
|
This function compute the Extended Euclidean algorithm
|
|
https://user.eng.umd.edu/~danadach/Cryptography_20/ExtEuclAlg.pdf
|
|
https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
|
|
|
|
Args:
|
|
a (Integer): the number a
|
|
b (Integer): the number b
|
|
"""
|
|
if a == 0:
|
|
return b, 0, 1
|
|
gcd, x1, y1 = egcd(b % a, a)
|
|
x = y1 - (b // a) * x1
|
|
y = x1
|
|
return gcd, x, y
|
|
|