Return the modular inverse of a % m, which is the number x such that a*x % m = 1
(a, m)
| 147 | |
| 148 | |
| 149 | def findModInverse(a, m): |
| 150 | """Return the modular inverse of a % m, which is the number x such |
| 151 | that a*x % m = 1""" |
| 152 | |
| 153 | if gcd(a, m) != 1: |
| 154 | # No mod inverse exists if a & m aren't relatively prime: |
| 155 | return None |
| 156 | |
| 157 | # Calculate using the Extended Euclidean Algorithm: |
| 158 | u1, u2, u3 = 1, 0, a |
| 159 | v1, v2, v3 = 0, 1, m |
| 160 | while v3 != 0: |
| 161 | q = u3 // v3 # Note that // is the integer division operator |
| 162 | v1, v2, v3, u1, u2, u3 = ((u1 - q * v1), |
| 163 | (u2 - q * v2), |
| 164 | (u3 - q * v3), |
| 165 | v1, v2, v3) |
| 166 | return u1 % m |
| 167 | |
| 168 | |
| 169 | # If this program was run (instead of imported), run the program: |