Modular Exponentiation

Modular exponentiation is a fundamental operation in number theory and cryptography. It involves calculating the remainder when an integer, raised to a positive integer power, is divided by another positive integer, known as the modulus.

Mathematically, if we have three integers $a$, $b$, and $m$, where $a$ is the base, $b$ is the exponent, and $m$ is the modulus, then modular exponentiation computes:

$$a^b \pmod{m}$$

The straightforward approach to calculate this involves computing $a^b$ first and the finding the modulo $m$, which can become impractical for large numbers. However, by exploiting modular arithmetic properties, we can perform the calculation more efficiently.

One common algorithm for modular exponentiation is the binary exponentiation method, also known as exponentiation by squaring. This algorithm reduces the number of multiplications required to compute the result.

Here's how the binary exponentiation algorithm works:

• Start with the result $r$ initialized to 1.
• Iterate through the binary representation of the exponent $b$ from right to left.
• At each step, square the base $a$ modulo $m$ (i.e., $a^2 \pmod{ m}$).
• If the current bit of $b$ is 1, multiply the current result $r$ by $a \pmod{m}$.
• Continue this process until all bits of $b$ are processed.
• The final result $r$ is the modular exponentiation of $a^b \pmod{m}$.

Example:

lets compute $5^{13} \pmod{7}$

$13=1101 $ in binary

So we start from LSB and compute powers of 5.

$5^8.5^4.5^2.5^1=4.2.4.5$

wherever the bit is 1 we multiply the result to $r$ So $r= 4.2.5=40 \equiv 5 \pmod{7}$

Python code

def square_and_multiply(base, exponent, modulus):
    result = 1
    base = base % modulus
while exponent > 0:

    # If current bit is 1, multiply result by base modulo modulus
    if exponent % 2 == 1:
        result = (result * base) % modulus
print(exponent,":",base,":",result)
# Square the base modulo modulus
base = (base * base) % modulus
# Divide the exponent by 2 (right shift)
exponent = exponent >> 1
return result

result = square_and_multiply(5, 13, 7)
print("Result of 5^13 mod 7 =", result)

print("using the pow function=",pow(5,13,7))

13 : 5 : 5
6 : 4 : 5
3 : 2 : 3
1 : 4 : 5
Result of 5^13 mod 7 = 5

using the pow function=5