# Modular Exponentiation Notes

## What Is Modular Exponentiation?

Modular exponentiation is exponentiation performed over a modulus.
Simply, it is about calculating a power of a number, then taking the result modulo (remainder after division by) another number.
It’s written like this:
$$ b^e \pmod m $$

In that expression, we'd refer to $b$ as the base, to $e$ as the exponent, and to $m$ as the modulus.

---

### How not to implement modular exponentiation

A really bad approach to implementing modular exponentiation would be something like this: `a ** b % m`, which uses the definition quite literally.

The larger the exponent `b` is, the worse computing `a ** b` becomes.
It is very slow, uses a lot of memory, may cause overflows, and simply - is not efficient.

So instead, we use the **fast modular exponentiation** algorithm, also called **exponentiation by squaring**, which computes the same result efficiently.

---

## Example
Let's calculate `3^13 mod 7` using the Fast Exponentiation Algorithm.

First, write 13 in binary:

13 = 1101 (binary)

So:

3^13 = 3^(8 + 4 + 0 + 1)
     = 3^8 * 3^4 * 3^1

Compute powers of 3 mod 7 by squaring each time:

3^1 = 3           → 3 mod 7 = 3
3^2 = 9           → 9 mod 7 = 2
3^4 = (3^2)^2 = 2^2 = 4 mod 7
3^8 = (3^4)^2 = 4^2 = 16 mod 7 = 2

Now multiply the powers mod 7:

3^13 mod 7 = 3^8 * 3^4 * 3^1 mod 7
           = 2 * 4 * 3 = 24
           = 24 mod 7 = 3

`3^13 mod 7 = 3`

---

## Python Implementation of Fast Modular Exponentiation

def fast_mod_exp(base, exponent, modulus):
    result = 1
    base %= modulus  # Handle case where base > modulus

    while exponent > 0:
        if exponent % 2 == 1:
            # If the current bit is 1, multiply result by base
            result = (result * base) % modulus
        # Square the base
        base = (base * base) % modulus
        # Move to next bit
        exponent = exponent // 2

    return result

## Python's `pow()` and Sagemath's `power_mod`
Both [`pow(a, b, m)`](https://docs.python.org/3/library/functions.html#pow) in Python and [`power_mod(a, b, m)`](https://doc.sagemath.org/html/en/reference/rings_standard/sage/arith/misc.html#sage.arith.misc.power_mod) in SageMath are optimized for modular exponentiation and are fast and reliable.

You can use them to verify our previous exapmle calculation is correct in code:

>>> pow(3, 13, 7)
3

sage: power_mod(3, 13, 7)
3

---

Both `pow` and `power_mod` support negative exponents for calculating [modular multiplicative inverses](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse):

>>> pow(2, -1, 7)
4
>>> (2 * 4) % 7
1

sage: power_mod(2, -1, 7)
4
sage: (2 * 4) % 7
1

They are computed efficiently using the [Extended Euclidean Algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm).

---

Sage's `power_mod` function is even more powerful, as it can even handle symbols:

sage: R.<x> = ZZ[]
sage: power_mod(3*x, 10, 7)                                          
4*x^10
sage: power_mod(-3*x^2 + 4, 7, 2*x^3 - 5)
x^14 + x^8 + x^6 + x^3 + 962509*x^2 - 791910*x - 698281

Generally, it would also work as long as the base and the modulus are elements of a ring that implements the modulo operator %.