Modular Exponentiation Calculator — aᵇ mod m
Compute aᵇ mod m for huge exponents with fast square-and-multiply: the result, the binary form of b, every squaring step in a table and the number of multiplications used.
How it works
Write b in binary, b = Σ bᵢ·2ⁱ · aᵇ = ∏ (a^(2^i))^(bᵢ) · repeatedly square: a^(2^(i+1)) = (a^(2^i))² mod m · multiply the result by a^(2^i) mod m whenever bit bᵢ = 1 · reduce mod m after every step
Raising a number to a huge power and then reducing would need astronomically large intermediate values. Modular exponentiation avoids that by reducing after every multiplication, which is allowed because (x·y) mod m = ((x mod m)(y mod m)) mod m. The right-to-left binary method squares the base once per bit of the exponent and multiplies it into the result for each 1-bit, so it needs only about log₂ b steps. This is the core operation of RSA, Diffie–Hellman and primality tests (Knuth, The Art of Computer Programming Vol. 2, §4.6.3). All arithmetic here uses exact big integers.
Worked example
4¹³ mod 497: 13 = 1101 in binary. Squares mod 497: 4, 16, 256, 256² = 65,536 mod 497 = 429. Multiply the ones for bits 0, 2 and 3: 4 × 256 = 1,024 mod 497 = 30, then 30 × 429 = 12,870 mod 497 = 445. So 4¹³ mod 497 = 445 (check: 4¹³ = 67,108,864 = 135,027 × 497 + 445).
Sources: Wolfram MathWorld — Modular Exponentiation (Power) · Wikipedia — Modular exponentiation (right-to-left binary method)
Frequently asked questions
How do you calculate a large power mod n by hand?
Write the exponent in binary, build the table a, a², a⁴, a⁸, … reducing mod n each time, then multiply together the entries that match the 1-bits and reduce again.
Why not compute aᵇ first and then take the remainder?
For exponents in the hundreds or thousands aᵇ has more digits than any calculator can hold. Reducing at every step keeps every number smaller than m².
Can Fermat’s or Euler’s theorem make it faster?
Yes. If gcd(a, m) = 1 you can reduce the exponent modulo φ(m) first, since a^φ(m) ≡ 1 (mod m). For a prime modulus p, φ(p) = p − 1.
What is 0⁰ mod m here?
The calculator follows the usual convention 0⁰ = 1, so 0⁰ mod m = 1 (or 0 when m = 1).
Related calculators
This calculator is for educational purposes. Double-check important results before acting on them.