# How to Calculate Modular Multiplicative Inverse in Python

Suraj Joshi Feb 02, 2024

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:

• ##### The approach begins by setting up a loop that iterates over x within a specified range. This range is typically [1, m-1], as the modular multiplicative inverse must be within this range.
for x in range(1, m):

• ##### For each value of x, the approach checks whether the condition (a * x) % m = 1 is satisfied. If x satisfies this condition, it means that x is the modular multiplicative inverse of the integer a under modulo m.
• (a * x) calculates the product of a and x.
• (a * x) % m calculates the remainder when the product is divided by m.
• If the remainder is 1, it means that x is the modular multiplicative inverse of the integer a under modulo m.
• ##### If the condition is met for a particular x value, the function returns x as the modular multiplicative inverse.
return x

• ##### If none of the x values within the specified range satisfy the condition (a * x) % m = 1, the approach raises an exception. This indicates that the modular multiplicative inverse does not exist for the given a and m because they are not coprime (i.e., gcd(a, m) != 1).
raise Exception("The modular inverse does not exist.")

• ##### The function returns the modular multiplicative inverse if it exists or raises an exception if it does not.

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:

• ##### The method takes two integers as input - a and m, where a is the number for which we want to find the modular multiplicative inverse, and m is the modulo value.
• It is assumed that a and m are positive integers, and m is greater than 1.
• Furthermore, it’s essential to ensure that a and m are coprime (i.e., gcd(a, m) = 1).
• ##### Calculate x using the Modular Exponentiation method. The goal is to find x such that (a * x) % m = 1.
• To do this, we raise a to the power of -1 modulo m. This is because (a^(-1) % m) yields the modular multiplicative inverse of the integer a under modulo m.
• Mathematically, it can be expressed as: x = (a^(-1)) % m.
• ##### Return the result. The calculated value of x is the modular multiplicative inverse of a under modulo m.

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:

• ##### Use the Extended Euclidean Algorithm to calculate the GCD of a and m (i.e., gcd(a, m)).
• If the GCD is not 1, it means that a and m are not coprime, and the modular multiplicative inverse does not exist. In this case, the algorithm terminates.
• If the GCD is 1, it means a and m are coprime, and the algorithm proceeds to calculate the Bézout coefficients x and y such that ax + my = 1. These coefficients are essential to finding the modular multiplicative inverse.
• ##### Return the result:
• The Bézout coefficients x and y are calculated as part of the Extended Euclidean Algorithm. We are interested in x because it is the modular multiplicative inverse.
• The calculated x is returned as the modular multiplicative inverse of a under modulo m.

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:

$$[a^{p-1} \equiv 1 \pmod{p}]$$

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:

$$[x \equiv a^{m-2} \pmod{m}]$$

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.

Author: Suraj Joshi

Suraj Joshi is a backend software engineer at Matrice.ai.