Instantly share code, notes, and snippets.

Embed
What would you like to do?
Modular Multiplicative Inverse
def greatest_common_divisor_extended(a, b):
'''
擴展歐幾里得算法 (Extended Euclidean algorithm)
'''
if b == 0:
return a, 1, 0
gcd, y, x = greatest_common_divisor_extended(b, a % b)
return gcd, x, y - (a // b) * x
def inverse_modular(a, b):
'''
Mod 反元素 (Modular Multiplicative Inverse)
'''
gcd, x, y = greatest_common_divisor_extended(a, b)
return x % b
a, b = 43, 26
c = inverse_modular(a, b)
print(c)
print()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment