How to Calculate Modular Multiplicative Inverse in Python

1. Calculate Modular Multiplicative Inverse Using the Naive Iterative Approach
2. Calculate Modular Multiplicative Inverse Using Modular Exponentiation
3. Calculate Modular Multiplicative Inverse Using the Extended Euclidean Algorithm
4. Calculate Modular Multiplicative Inverse in Python Using Fermat’s Little Theorem
5. Conclusion

The modular multiplicative inverse plays a crucial role in modular arithmetic, cryptography, and various mathematical applications. It is important to note that not all integers have a modular multiplicative inverse.

For the inverse to exist, a and m must be coprime, meaning their greatest common divisor (GCD) is equal to 1 (i.e., gcd(a, m) = 1).

If a and m are not coprime, the modular multiplicative inverse does not exist for that pair. In such cases, it’s important to verify the coprimality of a and m before attempting to find the inverse.

In this article, we will explore how to calculate the modular multiplicative inverse in Python.

Calculate Modular Multiplicative Inverse Using the Naive Iterative Approach

The naive iterative approach to finding the modular multiplicative inverse is straightforward but not the most efficient method.

It involves checking each integer in the range [1, m-1] to see if it satisfies the condition (a * x) % m = 1. This condition represents the definition of the modular multiplicative inverse.

Here’s a Python function that implements this approach:

def find_mod_inv(a, m):
    for x in range(1, m):
        if (a % m) * (x % m) % m == 1:
            return x
    raise Exception("The modular inverse does not exist.")

Let’s break down how this approach works step by step:

Let’s consider an example to find the modular multiplicative inverse of 13 under modulo 22:

def find_mod_inv(a, m):
    for x in range(1, m):
        if (a % m) * (x % m) % m == 1:
            return x
    raise Exception("The modular inverse does not exist.")


a = 13
m = 22

try:
    res = find_mod_inv(a, m)
    print("The required modular inverse is: " + str(res))
except Exception as e:
    print("The modular inverse does not exist.")

Output:

The required modular inverse is: 17

In this example, we successfully found that the modular multiplicative inverse of 13 under modulo 22 is 17. This value satisfies the condition (13 * 17) % 22 = 1.

Calculate Modular Multiplicative Inverse Using Modular Exponentiation

The Modular Exponentiation method is a powerful algorithm to find the modular multiplicative inverse efficiently, especially when working with large numbers. It is based on the properties of modular arithmetic and the concept of repeated squaring and multiplication.

Here’s how the Modular Exponentiation method works:

Let’s implement the Modular Exponentiation method in Python:

def mod_inverse(a, m):
    if math.gcd(a, m) != 1:
        raise ValueError("Modular inverse does not exist")
    return pow(a, -1, m)

In this implementation:

• We check whether a and m are coprime. If they are not, we raise an exception because the modular multiplicative inverse does not exist.

• We calculate x using the pow function with exponent -1 and modulo m.

Let’s find the modular multiplicative inverse of 13 under modulo 22 using the Modular Exponentiation method:

import math


def mod_inverse(a, m):
    if math.gcd(a, m) != 1:
        raise ValueError("Modular inverse does not exist")
    return pow(a, -1, m)


a = 13
m = 22

try:
    res = mod_inverse(a, m)
    print("The required modular inverse is: " + str(res))
except ValueError as e:
    print("The modular inverse does not exist.")

Output:

The required modular inverse is: 17

In this example, we successfully found that the modular multiplicative inverse of 13 under modulo 22 is 17 using the Modular Exponentiation method.

This method is efficient and suitable for both small and large values of a and m, provided they are coprime.

Calculate Modular Multiplicative Inverse Using the Extended Euclidean Algorithm

The Extended Euclidean Algorithm is another method for finding the modular multiplicative inverse efficiently. It is particularly useful when m is a prime number, but it can also be used for any m as long as a and m are coprime.

The algorithm works as follows:

Let’s implement the Extended Euclidean Algorithm in Python:

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = extended_gcd(b % a, a)
        return (g, y - (b // a) * x, x)


def mod_inverse(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError("Modular inverse does not exist")
    else:
        return x % m

In this implementation:

• The extended_gcd function calculates the GCD and Bézout coefficients x and y using recursion.

• The mod_inverse function checks whether a and m are coprime. If they are, it calculates x and returns it as the modular multiplicative inverse.

Let’s find the modular multiplicative inverse of 13 under modulo 22 using the Extended Euclidean Algorithm:

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = extended_gcd(b % a, a)
        return (g, y - (b // a) * x, x)


def mod_inverse(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError("Modular inverse does not exist")
    else:
        return x % m


a = 13
m = 22

try:
    res = mod_inverse(a, m)
    print("The required modular inverse is: " + str(res))
except ValueError as e:
    print("The modular inverse does not exist.")

Output:

The required modular inverse is: 17

In this example, we successfully found that the modular multiplicative inverse of 13 under modulo 22 is 17 using the Extended Euclidean Algorithm.

Calculate Modular Multiplicative Inverse in Python Using Fermat’s Little Theorem

Fermat’s Little Theorem is a significant result in number theory that provides a way to find the modular multiplicative inverse. The theorem states that if the variable p is a prime number and a is an integer not divisible by p, then:

In this equation, a is the base, p is the prime modulo, and p-1 is the exponent.

To find the modular multiplicative inverse x of a under modulo m, we can use Fermat’s Little Theorem if m is prime and a is not divisible by m. The modular inverse can be calculated as follows:

This method is highly efficient when m is prime, making it a valuable tool in cryptography and number theory.

Let’s implement the calculation of the modular multiplicative inverse using Fermat’s Little Theorem in Python:

def mod_inverse(a, m):
    if is_prime(m):
        if a < 1 or a >= m:
            raise ValueError("Invalid input: 'a' must be in the range [1, m-1]")
        return pow(a, m - 2, m)
    else:
        raise ValueError("Fermat's Little Theorem only applies when 'm' is prime.")


def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

In this implementation:

• The mod_inverse function first checks whether m is prime using the is_prime function. If m is prime and a is within the valid range [1, m-1], it calculates x using Fermat’s Little Theorem with pow(a, m - 2, m).

• The is_prime function checks if a number is prime, ensuring that the method is only used when m is prime.

Let’s find the modular multiplicative inverse of 13 under modulo 17 using Fermat’s Little Theorem:

def mod_inverse(a, m):
    if is_prime(m):
        if a < 1 or a >= m:
            raise ValueError("Invalid input: 'a' must be in the range [1, m-1]")
        return pow(a, m - 2, m)
    else:
        raise ValueError("Fermat's Little Theorem only applies when 'm' is prime.")


def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True


a = 13
m = 17

try:
    res = mod_inverse(a, m)
    print("The required modular inverse is: " + str(res))
except ValueError as e:
    print(e)

Output:

The required modular inverse is: 4

In this example, we successfully found that the modular multiplicative inverse of 13 under modulo 17 is 4 using Fermat’s Little Theorem.

Conclusion

In this article, we explored several methods for calculating the modular multiplicative inverse in Python, each with its advantages and use cases. These methods include the Naive Iterative Approach, Modular Exponentiation, the Extended Euclidean Algorithm, and Fermat’s Little Theorem.

• The Naive Iterative Approach is a straightforward method that checks each integer within a specified range to find the modular inverse. While it may not be the most efficient, it provides a clear and simple way to solve the problem.

• Modular Exponentiation offers an efficient algorithm, particularly suitable for large numbers. It leverages the principles of modular arithmetic and repeated squaring to find the inverse quickly.

• The Extended Euclidean Algorithm is a powerful method, especially when the modulo m is prime. It efficiently calculates the modular multiplicative inverse by determining the GCD and Bézout coefficients, ensuring that a and m are coprime.

• Fermat’s Little Theorem is a valuable tool when m is prime and a is not divisible by m. It provides an efficient and elegant solution to the problem by raising a to the power of m-2 modulo m.

In practice, the choice of method depends on factors such as the size of the numbers, the properties of a and m, and the computational resources available. By understanding and applying these methods, you can confidently tackle modular multiplicative inverse problems in Python and apply them to a wide array of mathematical and cryptographic challenges.