Modular Exponentiation

Modular Exponentiation#

Modular exponentiation involves raising a number to an exponent and then taking the remainder when the result is divided by the modulus. This operation is commonly used in fields such as cryptography.

The formula for modular exponentiation of a number \(a\) raised to an exponent \(b\) with modulus \(m\) is:

\[a^b~\mod~m\]

Steps to Perform Modular Exponentiation#

  1. Compute the Power \(a^b\): Calculate the power of the base \(a\) raised to the exponent \(b\).

  2. Apply the Modulus \(m\): After computing \(a^b\), take the remainder when the result is divided by the modulus \(m\).

However, computing \(a^b\) directly for large \(b\) can be computationally expensive and may result in very large intermediate results. Instead, we use an efficient method called Exponentiation by Squaring to perform modular exponentiation.

Exponentiation by Squaring#

Exponentiation by Squaring is an efficient algorithm to compute \(a^b \mod m\). It works by breaking down the exponentiation process into a series of squaring and multiplication steps, reducing the overall number of operations.

Steps of Exponentiation by Squaring:#

  1. Initialisation: Set the result to 1 and the base to \(a\).

  2. Iterate through the bits of the exponent \(b\):

    • If the current bit is 1, multiply the result by the current base.

    • Square the base for the next iteration.

  3. Apply the modulus \(m\) at each step: Take the remainder of both the result and the base with \(m\) to keep the numbers manageable.

Functions#

This time we will make two functions from the get go, one to initially show how to get the result, and one that can give you the steps for the Exponentiation by Squaring method.

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

def modular_exponentiation(base, exponent, modulus):
    result = pow(base, exponent, modulus)
    print(f"{base}^{exponent} ≡ {result} (mod {modulus})")
    return result

def modular_exponentiation_steps(base, exponent, modulus):
    result = 1
    base = base % modulus
    steps = []

    while exponent > 0:
        if (exponent % 2) == 1:
            result = (result * base) % modulus
            steps.append(f"Result updated to {result} after multiplying by base {base}")
        
        base = (base * base) % modulus
        steps.append(f"Base squared and reduced modulo {modulus}: {base}")

        exponent = exponent // 2
        steps.append(f"Exponent shifted right: {exponent}")

    print(f"Steps of computation:")
    for step in steps:
        print(step)

    print(f"{base}^{exponent} ≡ {result} (mod {modulus})")
    return result

Examples#

Finding the modular exponentiation of \(11^{13}~mod~18\)#

a = 11
exponent = 13
modulus = 18

result = modular_exponentiation(a, exponent, modulus)

11^13 ≡ 11 (mod 18)

result = modular_exponentiation_steps(a, exponent, modulus)

Steps of computation:
Result updated to 11 after multiplying by base 11
Base squared and reduced modulo 30: 1
Exponent shifted right: 6
Base squared and reduced modulo 30: 1
Exponent shifted right: 3
Result updated to 11 after multiplying by base 1
Base squared and reduced modulo 30: 1
Exponent shifted right: 1
Result updated to 11 after multiplying by base 1
Base squared and reduced modulo 30: 1
Exponent shifted right: 0
1^0 ≡ 11 (mod 30)

Finding the modular exponentiation of \(283^{4}~mod~12\)#

a = 283
exponent = 4
modulus = 12

result = modular_exponentiation(a, exponent, modulus)

283^4 ≡ 1 (mod 12)

result = modular_exponentiation_steps(a, exponent, modulus)

Steps of computation:
Base squared and reduced modulo 12: 1
Exponent shifted right: 2
Base squared and reduced modulo 12: 1
Exponent shifted right: 1
Result updated to 1 after multiplying by base 1
Base squared and reduced modulo 12: 1
Exponent shifted right: 0
1^0 ≡ 1 (mod 12)

Finding the modular exponentiation of \(38273^{7}~mod~24\)#

a = 38273
exponent = 7
modulus = 24

result = modular_exponentiation(a, exponent, modulus)

38273^7 ≡ 17 (mod 24)

result = modular_exponentiation_steps(a, exponent, modulus)

Steps of computation:
Result updated to 17 after multiplying by base 17
Base squared and reduced modulo 24: 1
Exponent shifted right: 3
Result updated to 17 after multiplying by base 1
Base squared and reduced modulo 24: 1
Exponent shifted right: 1
Result updated to 17 after multiplying by base 1
Base squared and reduced modulo 24: 1
Exponent shifted right: 0
1^0 ≡ 17 (mod 24)
Contents