Modular Exponentiation by Repeated Squaring

Modular exponentiation by repeated squaring

Modular exponentiation means finding the value of an expression like (a^n \bmod m) efficiently. The key idea is to avoid expanding (a^n) directly, since that becomes very large. Instead, use repeated squaring and reduce modulo (m) at every step.

1) Break the exponent into powers of 2

Write the exponent as a sum of powers of 2. For example, 13 = 8 + 4 + 1. This tells you which squared powers you need.

2) Build powers by squaring

Start with (a), then compute (a^2), (a^4), (a^8), and so on. After each squaring, take the remainder modulo (m). This keeps the numbers small and manageable.

3) Combine only the needed terms

Multiply the modular values corresponding to the powers used in the exponent. Reduce modulo (m) after each multiplication.

4) Check your work

A quick check is to verify that every intermediate result is between 0 and (m-1). If the exponent is small, you can also compare with direct computation to confirm the final remainder.

Example strategy

If you need (a^{13} \bmod m), compute (a^1), (a^2), (a^4), and (a^8) modulo (m), then combine (a^8 \cdot a^4 \cdot a^1) modulo (m).

This method is reliable, fast, and designed for exact final answers.