calcfluent

Modular Exponentiation Calculator

Calculate a to the power b modulo m for numbers of any practical size, with the binary square-and-multiply trace, modular inverses and Euler's theorem check.

Negative exponents use the modular inverse of a.
Positive whole number, up to 400 digits.
gcd(a, m)
1a is invertible mod m
Exponent in binary
1101
Operations used
3 squarings, 3 multiplications
Euler’s φ(m)
420m is composite
4^13 mod 497445

Show the work

  1. Write the exponent in binary: 13 = 11012 (4 bits)
  2. Square-and-multiply: scan the bits from left to right; square the running result at every bit, and also multiply by the base when the bit is 1, reducing mod m after each operation
  3. After 4 bits: 3 squarings and 3 multiplications instead of 12 repeated multiplications
  4. Result: 413 mod 497 = 445
  5. Check with Euler’s theorem: gcd(a, m) = 1, so aφ(m) ≡ 1 and the exponent can be reduced mod φ(497) = 420: 13 mod 420 = 13
Square-and-multiply trace (all values mod m)
StepBitStartSquaredMultiply by a?Result
1111× 4 → 44
21416× 4 → 6464
3064120—120
41120484× 4 → 445445

Modular exponentiation computes the remainder when a power ab is divided by a modulus m, written ab mod m. It is how computers handle the enormous powers behind encryption, digital signatures and primality tests. This calculator works with exact whole numbers of up to 400 digits, uses the fast square-and-multiply method, and shows every step in a trace table, including negative exponents through modular inverses and a check with Euler’s theorem.

How to use the modular exponentiation calculator

  1. Enter the base a. Negative bases are reduced modulo m first.
  2. Enter the exponent b. A negative exponent is handled by inverting a modulo m, which requires gcd(a, m) = 1.
  3. Enter the modulus m, a positive whole number.
  4. Read the result on the tape, then follow the trace: one row per binary digit of the exponent.

How square-and-multiply works

Write the exponent in binary, b = (bk−1 … b1 b0)2. Starting with r = 1, process the bits from the most significant to the least:

r ← r² mod m,   then if the bit is 1: r ← r × a mod m

Each squaring doubles the exponent accumulated so far, and each multiplication adds one, so after the last bit r = ab mod m. A k-bit exponent needs at most k − 1 squarings and k multiplications. Two facts justify reducing at every step:

(x × y) mod m = [(x mod m) × (y mod m)] mod m  ·  aφ(m) ≡ 1 (mod m) when gcd(a, m) = 1

Worked example

Compute 413 mod 497.

  1. In binary, 13 = 11012.
  2. Bit 1: square 1 to get 1, multiply by 4 → 4 (this is 41).
  3. Bit 1: square 4 to get 16, multiply by 4 → 64 (43).
  4. Bit 0: square 64 to get 4,096 mod 497 = 120 (46).
  5. Bit 1: square 120 to get 14,400 mod 497 = 484, multiply by 4 → 1,936 mod 497 = 445 (413).

So 413 mod 497 = 445, found with 3 squarings and 3 multiplications. No intermediate value exceeded 497² = 247,009, even though 413 itself is 67,108,864.

A second example shows why primality tests need care: 7560 mod 561 = 1, exactly what Fermat’s little theorem predicts for a prime. Yet 561 = 3 × 11 × 17 is composite. It is the smallest Carmichael number, which fools the Fermat test for every base coprime to it; the calculator flags such cases as Fermat pseudoprimes.

Applications

RSA in miniature

With primes 61 and 53, the modulus is n = 3,233 and φ(n) = 3,120. Choosing public exponent e = 17 gives private exponent d = 2,753, since 17 × 2,753 ≡ 1 (mod 3,120). Encrypting the message 65 gives 6517 mod 3,233 = 2,790, and decrypting gives 2,7902,753 mod 3,233 = 65 again. Real RSA uses the same arithmetic with moduli of 2,048 bits or more.

Reducing the exponent

When gcd(a, m) = 1, Euler’s theorem allows b to be replaced by b mod φ(m). For a prime p, φ(p) = p − 1, so 31,000,000 mod 7 equals 31,000,000 mod 6 = 3⁴ mod 7 = 4.

For a single remainder, use the modulo calculator. The modular inverse comes from the extended version of the algorithm shown in the Euclid’s algorithm calculator, and the prime number checker confirms whether a modulus is prime.

Frequently asked questions

Why not just calculate a^b and then take the remainder?

Because a^b gets astronomically large. 7^560 already has 474 digits, and the exponents used in cryptography have hundreds of digits themselves, producing numbers with more digits than there are atoms in the universe. Reducing modulo m after every multiplication keeps every intermediate value smaller than m², so the work stays small.

How does square-and-multiply work?

Write the exponent in binary. Starting from 1, read the bits from left to right: square the running result at each bit, and multiply by the base as well whenever the bit is 1. Each step doubles the exponent built so far and optionally adds one, so after the last bit the result equals a^b. It needs about 2 log₂ b multiplications instead of b − 1.

What does a negative exponent mean in modular arithmetic?

a^(−k) mod m means the k-th power of the modular inverse of a, the number x with a·x ≡ 1 (mod m). It exists only when a and m have no common factor. For example 3^(−1) mod 11 = 4, because 3 × 4 = 12 ≡ 1 (mod 11).

How does Fermat's little theorem help?

If p is prime and a is not a multiple of p, then a^(p−1) ≡ 1 (mod p). More generally, Euler's theorem says a^φ(m) ≡ 1 (mod m) when gcd(a, m) = 1, so the exponent can be reduced modulo φ(m) before computing. The calculator shows φ(m) for moduli up to one trillion.

Where is modular exponentiation used?

It is the core operation of RSA encryption and digital signatures, Diffie–Hellman key exchange, and primality tests such as Fermat and Miller–Rabin. It also appears in hashing, pseudo-random number generators and competitive programming problems that ask for answers modulo 1,000,000,007.

Last reviewed October 2026 by the CalcFluent editorial team. How we check our calculators.