Modular Reduction - Modular Exponentiation

Modular exponentiation keeps numbers small by reducing after each operation. This lesson pins the modulus and the starting value.

highlighted = computed this step

Why the modulus is present

The modulus keeps every intermediate value inside a small exact remainder set. Here the modulus is 33.

m=33

The base is 7, and it already reduces to 7 modulo 33.

7\bmod{}33=7

After each square or multiply, the ladder keeps only the remainder modulo 33. That is why the table never needs the full power.

\text{keep remainders mod }33

The ladder starts with result 1 before reading exponent bits.

r_{\text{start}}=1

The first visible row squares start value 1, then multiplies by base 7 because the bit is 1. The row result is 7.

1\to7

Modular exponentiation keeps reducing after each operation, so every displayed row stays small and inspectable.

\text{reduce after every step}