Modular Inverse
Finds x such that a·x ≡ 1 (mod m), which exists exactly when gcd(a, m) = 1. Extended Euclid produces x directly as the Bézout coefficient of a, reduced into [0, m).
- Category
- Mathematics
- Time complexity
- O(log m)
- Space complexity
- O(log m)
Pseudocode
run extended Euclid on (a, m) if gcd ≠ 1: no inverse exists else: x from Bézout coefficients inverse = ((x mod m) + m) mod m
Reference implementation
def mod_inverse(a, m):
g, x, _ = extgcd(a, m)
if g != 1: raise ValueError("no inverse")
return (x % m + m) % m