Skip to content

Instantly share code, notes, and snippets.

@Francis-Lee-Earth

Francis-Lee-Earth/ModularMultiplicativeInverse.py

Last active October 11, 2018 12:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Francis-Lee-Earth/f5d16c22a2aac3457541df3844c8abd7 to your computer and use it in GitHub Desktop.
Save Francis-Lee-Earth/f5d16c22a2aac3457541df3844c8abd7 to your computer and use it in GitHub Desktop.
Download ZIP
Modular Multiplicative Inverse
Raw
ModularMultiplicativeInverse.py
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