Modular Exponentiation Calculator – baseᵉ mod m

Computing baseᵉ mod m by first forming baseᵉ explodes — 2¹⁰⁰⁰ has 302 digits — so the method squares and reduces mod m at every step, keeping numbers small. For 2¹⁰ mod 1000, exponent 10 = 1010₂: start with 2, square to 4, square to 16 and multiply to 32, square to 1024 ≡ 24. The calculator prints the binary expansion of the exponent, each squaring with its reduction, and the multiplications on the 1-bits. 3⁴ mod 5 squares twice: 3² = 9 ≡ 4, then 4² = 16 ≡ 1 — answer 1. Complexity is O(log e) multiplications, which is why RSA’s 65537 = 2¹⁶+1 exponent is chosen sparse: only 17 squarings plus one multiply. Fermat’s little theorem shortcut appears too: a^(p−1) ≡ 1 (mod p), collapsing exponents mod p−1 for prime moduli.

1. 1

   Enter base, exponent, modulus

   Such as 2, 10, 1000

2. 2

   Write the exponent in binary

   1010 for 10 guides the operations

3. 3

   Square and reduce

   Each step mods immediately: 4 → 16 → 256

4. 4

   Multiply on set bits

   Combine per the binary digits for the final 24

• 1

  Reduce after every multiply — numbers stay below m²

• 2

  Cost scales with log(exponent), not the exponent itself

• 3

  For prime m, cut the exponent mod m−1 (Fermat)

• Building the full power before reducing — overflow

• Skipping a reduction between squarings on large inputs

• Forgetting the final multiply for the low bit

• Applying Fermat reduction when m is composite