Skip to content

Instantly share code, notes, and snippets.

@bee-san
Created October 19, 2015 19:38
Show Gist options
  • Save bee-san/ae1909aee34f4fcfea4e to your computer and use it in GitHub Desktop.
Save bee-san/ae1909aee34f4fcfea4e to your computer and use it in GitHub Desktop.
Cryptomath
def gcd(a, b):
# Return the GCD of a and b using Euclid's Algorithm
while a != 0:
a, b = b % a, a
return b
def findModInverse(a, m):
# Returns the modular inverse of a % m, which is
# the number x such that a*x % m = 1
if gcd(a, m) != 1:
return None # no mod inverse if a & m aren't relatively prime
# Calculate using the Extended Euclidean Algorithm:
u1, u2, u3 = 1, 0, a
v1, v2, v3 = 0, 1, m
while v3 != 0:
q = u3 // v3 # // is the integer division operator
v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
return u1 % m
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment