TheAlgorithms/Python · error · ValueError

mod inverse of {a!r} and {m!r} does not exist

Error message

mod inverse of {a!r} and {m!r} does not exist

What it means

Raised by find_mod_inverse(a, m) in ciphers/cryptomath_module.py when gcd(a, m) != 1, i.e. a has no modular inverse modulo m. This is a mathematical precondition failure, not a bug: the extended Euclidean algorithm only yields an inverse for coprime operands.

Source

Thrown at ciphers/cryptomath_module.py:7

from maths.greatest_common_divisor import gcd_by_iterative


def find_mod_inverse(a: int, m: int) -> int:
    if gcd_by_iterative(a, m) != 1:
        msg = f"mod inverse of {a!r} and {m!r} does not exist"
        raise ValueError(msg)
    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

View on GitHub (pinned to f5988cc097)

Solutions

1. Choose a value of a coprime to m (check gcd(a, m) == 1 first)
2. For RSA: pick a different exponent e, commonly 65537, or different primes p and q
3. For affine ciphers mod 26: restrict a to {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}

Example fix

# before
inv = find_mod_inverse(e, phi)  # may raise if gcd(e, phi) != 1

# after
from maths.greatest_common_divisor import gcd_by_iterative as gcd
if gcd(e, phi) != 1:
    raise SystemExit("pick e coprime to phi")
inv = find_mod_inverse(e, phi)

from maths.greatest_common_divisor import gcd_by_iterative as gcd
assert gcd(a, m) == 1, f"{a} has no inverse mod {m}"

try:
    inv = find_mod_inverse(a, m)
except ValueError:
    # no inverse exists; pick different parameters
    raise

When it happens

Trigger: find_mod_inverse(4, 8) (gcd is 4); RSA key generation where e shares a factor with phi(n); affine cipher setup with a not coprime to 26.

Common situations: RSA implementations picking an exponent e that is not coprime to (p-1)(q-1); hill/affine cipher key selection where the multiplier must be invertible mod alphabet size; reusing parameters after changing modulus size.

Related errors

• factorial() not defined for negative values
• surface_area_cube() only accepts non-negative values
• surface_area_cuboid() only accepts non-negative values
• surface_area_sphere() only accepts non-negative values
• surface_area_hemisphere() only accepts non-negative values

AI-assisted analysis of TheAlgorithms/Python@f5988cc097 (2026-08-14). Data as JSON: /api/errors/5ff96f75db12cd06. Report an issue: GitHub.