Modular Inverse

Modular Inverse#

The modular inverse of a number \(a\) modulo \(m\) is a number \(x\) such that:

\[ a \times x \equiv 1 \mod m \]

The modular inverse exists if and only if \(a\) and \(m\) are coprime (i.e., \(\text{gcd}(a, m) = 1\)).

To find the modular inverse of \(a\) modulo \(m\), you can use the Extended Euclidean Algorithm.

Extended Euclidean Algorithm#

The Euclidean Algorithm is a method to find the greatest common divisor (gcd) of two integers. The Extended Euclidean Algorithm extends this to find the coefficients \(x\) and \(y\) such that:

\[ a \times x + b \times y = \text{gcd}(a, b) \]

These coefficients \(x\) and \(y\) can be used to express the gcd as a linear combination of \(a\) and \(b\).

Hide code cell source 
import sympy as sp
from sympy import *
from math import gcd

def modular_inverse(a, modulus):
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y
    
    gcd, x, _ = extended_gcd(a, modulus)
    if gcd != 1:
        raise ValueError(f"Inverse does not exist for {a} modulo {modulus}")
    else:
        result = x % modulus
        print(f"Inverse of {a} ≡ {result} (mod {modulus})")
        return result

Finding the modular inverse of \(23~mod~26\)#

a = 23
modulus = 26

result = modular_inverse(a, modulus)

Inverse of 23 ≡ 17 (mod 26)

Modular Inverse Calculation

To find the modular inverse of 23 mod 26, follow these steps using the Extended Euclidean Algorithm:

  1. Initialisation: Set initial values:

    • \(\text{gcd} = 1\)

    • \(x = 0\)

    • \(y = 1\)

  2. Step-by-Step Calculation:

    Step 0:

    • \(\text{gcd} = 1\)

    • \(x = 0\)

    • \(y = 1\)

    Step 1:

    • Update values based on the Euclidean algorithm:

    • \(\text{gcd} = 1\)

    • \(x = 1\)

    • \(y = 0\)

    Step 2:

    • Continue updating:

    • \(\text{gcd} = 1\)

    • \(x = -1\)

    • \(y = 1\)

    Step 3:

    • Further updates:

    • \(\text{gcd} = 1\)

    • \(x = 8\)

    • \(y = -1\)

    Step 4:

    • Final updates:

    • \(\text{gcd} = 1\)

    • \(x = -9\)

    • \(y = 8\)

  3. Result:

    • Since the \(\text{gcd}\) remains 1 throughout, 23 has an inverse modulo 26.

    • The final value of \(x\) after adjustments for modular arithmetic (as \(-9 \equiv 17 \ (\text{mod}\ 26)\)) gives the modular inverse.

    • Thus, the inverse of 23 modulo 26 is 17.

Extending the Function#

As modular inverse is a step up from the simple addition or subtraction operations in modular arithmetic; we can actually extend the function further to output the steps for using the Extended Euclidean Algorithm to find the modular inverse. This can be useful for understanding the steps, you can also use this to check your work for practicing the algorithm.

To add steps into a function you can actually use a list to store the steps and then return the list as well as the modular inverse. Where each time you want a step you do steps.append("Step") to add the step to the list.

def modular_inverse_steps(a, modulus):
    def extended_gcd(a, b):
        steps = []
        if a == 0:
            steps.append((b, 0, 1))
            return b, 0, 1, steps
        gcd, x1, y1, prev_steps = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        steps = prev_steps + [(gcd, x, y)]
        return gcd, x, y, steps

    gcd, x, y, steps = extended_gcd(a, modulus)
    if gcd != 1:
        raise ValueError(f"Inverse does not exist for {a} modulo {modulus}")
    else:
        result = x % modulus
        print(f"Steps to find the modular inverse of {a} mod {modulus}:")
        for i, (gcd, x, y) in enumerate(steps):
            print(f"Step {i}: gcd = {gcd}, x = {x}, y = {y}")
        print(f"Inverse of {a} ≡ {result} (mod {modulus})")
        return

Finding the modular inverse of \(11~mod~30\)#

a = 11
modulus = 30

result = modular_inverse_steps(a, modulus)

Steps to find the modular inverse of 11 mod 30:
Step 0: gcd = 1, x = 0, y = 1
Step 1: gcd = 1, x = 1, y = 0
Step 2: gcd = 1, x = -1, y = 1
Step 3: gcd = 1, x = 3, y = -1
Step 4: gcd = 1, x = -4, y = 3
Step 5: gcd = 1, x = 11, y = -4
Inverse of 11 ≡ 11 (mod 30)

Finding the modular inverse of \(23~mod~49\)#

a = 23
modulus = 49

result = modular_inverse_steps(a, modulus)

Steps to find the modular inverse of 23 mod 49:
Step 0: gcd = 1, x = 0, y = 1
Step 1: gcd = 1, x = 1, y = 0
Step 2: gcd = 1, x = -1, y = 1
Step 3: gcd = 1, x = 8, y = -1
Step 4: gcd = 1, x = -17, y = 8
Inverse of 23 ≡ 32 (mod 49)

Finding the modular inverse of \(20~mod~40\)#

In the following example you’ll see what occurs when the modular inverse doesn’t exist.

a = 20
modulus = 40

result = modular_inverse_steps(a, modulus)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In[22], line 4
      1 a = 20
      2 modulus = 40
----> 4 result = modular_inverse_steps(a, modulus)

Cell In[21], line 15, in modular_inverse_steps(a, modulus)
     13 gcd, x, y, steps = extended_gcd(a, modulus)
     14 if gcd != 1:
---> 15     raise ValueError(f"Inverse does not exist for {a} modulo {modulus}")
     16 else:
     17     result = x % modulus

ValueError: Inverse does not exist for 20 modulo 40
Contents