1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
# https://github.com/TheAlgorithms/Python/blob/98a4c2487814cdfe0822526e05c4e63ff6aef7d0/ciphers/cryptomath_module.py
def gcd(a: int, b: int) -> int:
while a != 0:
a, b = b % a, a
return b
def find_mod_inverse(a: int, m: int) -> int:
if gcd(a, m) != 1:
raise ValueError(f"mod inverse of {a!r} and {m!r} does not exist")
u1, u2, u3 = 1, 0, a
v1, v2, v3 = 0, 1, m
while v3 != 0:
q = u3 // v3
v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
return u1 % m
|
