Exponenciação Modular

Modular exponentiation: algorithm and example

Modular exponentiation gives you a^b mod n while never letting the monstrous intermediate a^b appear at all. The usual way to do this is exponentiation by squaring, also called binary exponentiation. You walk through the bits of b, square the running base mod n at each step, and fold that into the result whenever the current bit happens to be 1. The whole thing costs O(log b) multiplications.

Take 3^200 mod 50 as an example. You begin with 3² = 9, then 3⁴ = 81 mod 50 = 31, then 3⁸ = 31² mod 50 = 11, continuing that way and combining the squares whose bit positions add up to 200. When n = p is prime, Fermat's little theorem cuts the work down: a^(p−1) ≡ 1 (mod p) as long as gcd(a, p) = 1.

Applications

• RSA signing and encryption, where c = m^e mod n and e is usually 65537.
• Diffie–Hellman key exchange, where each side computes g^x mod p.
• ECDSA and the other elliptic-curve protocols that lean on fast modular powers.
• The Miller–Rabin primality test, plus cryptographic hashes that fold modular powers into the compression step.

FAQ

Why not just compute a^b and take mod n at the end? Because a^b can run to billions of digits. Reducing mod n on every step is what keeps the numbers from blowing up.

What if b is negative? Find the modular inverse of a first, then raise that to |b|.

Is binary exponentiation constant-time? Not on its own. A naive implementation branches on the bits of b, and that timing can leak the exponent. To close the side channel, cryptographic libraries reach for the Montgomery ladder or fixed-window variants.