Modular Exponentiation: How to Calculate a^b mod n Efficiently

Modular exponentiation computes a^b mod n without ever calculating a^b. Two ideas make it possible: reduce modulo n after every multiplication, and use repeated squaring so the number of multiplications grows with the number of digits in b rather than with b itself. Computing 7¹³ mod 11 takes four steps and never handles a number above 100, even though 7¹³ is 96,889,010,407.

The saving is not a convenience. For the numbers used in cryptography, where exponents run to hundreds of digits, the direct approach is not slow but impossible, and repeated squaring finishes in milliseconds.

This guide shows why the direct route fails, builds the method from two rules, works through examples with full step tables, gives pseudocode, and explains the speed difference in plain terms.

Why You Cannot Just Compute a^b

Take 7¹³ mod 11. The obvious plan is to work out 7¹³ and then divide by 11.

7¹³ = 96,889,010,407
96,889,010,407 = 11 × 8,808,091,855 + 2

The answer is 2, and the plan worked, but look at what it cost: an 11 digit intermediate value to produce a single digit answer.

Now scale it up. In RSA, a typical calculation is something like m^65537 mod n with n around 617 digits. The intermediate m^65537 would have millions of digits. No computer will store it, and no amount of waiting will help.

Two separate problems need solving:

1. The numbers get too big. Fixed by reducing modulo n at every step.
2. There are too many multiplications. Fixed by repeated squaring.

Rule 1: Reduce As You Go

The multiplication rule of modular arithmetic says you may replace any number by its remainder before multiplying:

If a ≡ b (mod n) and c ≡ d (mod n), then a · c ≡ b · d (mod n).

So a running product can be reduced after every single multiplication, and the final answer is unchanged.

Example. Compute 7⁵ mod 11 the slow way but reducing each time:

The answer is 10, and no number above 49 ever appeared. Compare that to 7⁵ = 16,807.

This alone solves the size problem. It does not solve the count problem: computing 7^65537 this way would still need 65,536 multiplications.

Rule 2: Repeated Squaring

Squaring doubles the exponent for the price of one multiplication.

7¹  ≡ 7               (mod 11)
7²  = 7 × 7   ≡ 5     (mod 11)
7⁴  = 5 × 5   ≡ 3     (mod 11)
7⁸  = 3 × 3   ≡ 9     (mod 11)
7¹⁶ = 9 × 9   ≡ 4     (mod 11)

Five multiplications reached exponent 16. Multiplying one at a time would have needed sixteen. The gap widens fast: ten squarings reach exponent 1,024, and twenty reach over a million.

The remaining question is how to build an arbitrary exponent out of these doubled ones. The answer is binary.

The Binary Exponent

Every whole number is a sum of distinct powers of 2, and its binary representation says which ones.

13 in binary is 1101

1101₂ = 8 + 4 + 0 + 1 = 13

So

7¹³ = 7⁸ · 7⁴ · 7¹

Every factor on the right is one of the squarings already computed. Substituting the reduced values:

7¹³ ≡ 9 × 3 × 7  (mod 11)
    = 189
    = 11 × 17 + 2
    ≡ 2          (mod 11)

Answer. 7¹³ ≡ 2 (mod 11), matching the brute-force result exactly, with no number above 189 involved.

That is the whole algorithm. Square repeatedly, and multiply in the squares whose bit is 1.

The Square-and-Multiply Algorithm

Written as a procedure that reads the exponent bit by bit from the right:

1. Set result = 1 and base = a mod n.
2. While the exponent is greater than 0:
   • If the exponent is odd, set result = (result × base) mod n.
   • Set base = (base × base) mod n.
   • Halve the exponent, discarding any remainder.
3. Return result.

The test “is the exponent odd” reads the lowest binary bit, and halving discards it, so the loop walks the binary representation from right to left. The Remainder Calculator confirms each individual reduction if you want to check a row by hand.

Worked trace: 7¹³ mod 11

The exponent sequence 13, 6, 3, 1 is just 13 halved repeatedly, and the base column holds 7, 7², 7⁴, 7⁸ reduced modulo 11.

Answer. 7¹³ ≡ 2 (mod 11). ✓

A Larger Example: 3⁴⁵ mod 101

Problem. Compute 3⁴⁵ mod 101.

For scale: 3⁴⁵ = 2,954,312,706,550,833,698,643, a 22 digit number. The algorithm never sees it.

The exponent 45 in binary is 101101, so 45 = 32 + 8 + 4 + 1.

Working the base column: 3² = 9, 9² = 81, 81² = 6561 = 101 × 64 + 97 so 97, then 97² = 9409 = 101 × 93 + 16 so 16, then 16² = 256 = 101 × 2 + 54 so 54.

Answer. 3⁴⁵ ≡ 32 (mod 101).

Verification. Reducing the exact value 2,954,312,706,550,833,698,643 modulo 101 also gives 32. ✓

Six steps, and the largest number handled was 9,409.

Finding the Last Two Digits of a Huge Power

“The last two digits of N” means N mod 100, which makes this a modular exponentiation question.

Problem. Find the last two digits of 7²²².

The number 7²²² has 188 digits, so the direct route is out.

Here a shortcut beats the general algorithm. Look at the powers of 7 modulo 100:

7¹ ≡ 7      7² ≡ 49     7³ ≡ 43     7⁴ ≡ 1     (mod 100)

The cycle closes at 4, so the powers repeat with period 4. Divide the exponent by 4 and keep the remainder:

222 = 4 × 55 + 2

So 7²²² lands where 7² lands:

7²²² ≡ 7² = 49  (mod 100)

Answer. The last two digits are 49.

This is the same as running square-and-multiply, but faster when a short cycle exists. Finding the cycle is only practical for small moduli; the general algorithm has no such restriction.

Shrinking the Exponent First

When the modulus is prime, Fermat’s little theorem reduces the exponent before any work starts.

If p is prime and does not divide a, then a^(p−1) ≡ 1 (mod p).

Problem. Compute 3²⁰⁰ mod 7.

Since 7 is prime, 3⁶ ≡ 1 (mod 7). Divide the exponent by 6:

200 = 6 × 33 + 2

So

3²⁰⁰ = (3⁶)³³ × 3² ≡ 1³³ × 9 ≡ 2  (mod 7)

Answer. 3²⁰⁰ ≡ 2 (mod 7), from one small division and one squaring.

For a composite modulus, Euler’s theorem does the same job using φ(n) in place of p − 1, provided gcd(a, n) = 1. Both results are the basis for finding a modular inverse by exponentiation.

Pseudocode

function modpow(a, b, n):
    if n == 1:
        return 0
    result = 1
    base   = a mod n
    while b > 0:
        if b is odd:
            result = (result * base) mod n
        base = (base * base) mod n
        b = b / 2        (integer division)
    return result

Three details make a real implementation correct:

• The n = 1 guard. Everything is congruent to 0 modulo 1, so the function must return 0 rather than 1.
• Reduce the base first. a mod n at the start keeps the first squaring small even if a is enormous.
• Watch for overflow. Two values just under n multiply to nearly n², so a 64 bit type overflows once n exceeds about 3 billion. Use a wide integer type, or a language with arbitrary precision integers.

In Python the whole thing is built in as a three argument pow:

pow(7, 13, 11)      # 2
pow(3, 45, 101)     # 32

pow(a, b, n) uses this exact algorithm internally, so it is both correct and fast. Writing 7 ** 13 % 11 gives the same answer for small inputs but builds the full power first, which is the thing to avoid.

How Much Faster Is It?

Count multiplications rather than seconds, since that is what changes.

The pattern is that square-and-multiply needs roughly 2 × (number of binary digits of b) multiplications, while the naive method needs b of them. Going from b to log₂(b) is what turns an impossible calculation into an instant one.

Each squaring costs one multiplication, and each 1 bit in the exponent costs one more, which is where the factor of 2 comes from.

Where It Is Used

• RSA encryption and decryption, which are exactly modular exponentiation with a large modulus.
• Diffie-Hellman key exchange, where both parties raise a shared base to a secret power modulo a large prime.
• Digital signatures such as DSA and its elliptic curve relatives.
• Primality testing. The Fermat and Miller-Rabin tests raise a base to a large power modulo the candidate.
• Hash chains and proof-of-work, wherever a value must be cheap to verify and expensive to reverse.

Common Mistakes

• Computing the power first, then reducing. 7 ** 222 % 100 works in Python only because Python has unlimited integers, and it is still enormously wasteful. In a fixed-width language it silently overflows and returns garbage.
• Forgetting to reduce the base at the start. If a is larger than n, reduce it before the loop.
• Reducing the exponent modulo n. The exponent does not live in the same world as the base. Reducing it needs Fermat or Euler, using p − 1 or φ(n), never n itself.
• Applying Fermat’s little theorem when p is not prime, or when p divides a. Both break the theorem.
• Overflow in the squaring step. Multiplying two numbers just below n needs room for n², not n.
• Missing the n = 1 case, which should return 0.
• Assuming a short cycle exists. Powers of 7 modulo 100 repeat every 4 steps, but powers modulo a large prime may not repeat until nearly p − 1 steps have passed.

Practice Problems

1. Compute 2¹⁰ mod 1000 by reducing as you go.
2. Compute 5⁶ mod 13 using repeated squaring.
3. Write 23 in binary and list the powers needed for a²³.
4. Compute 3¹¹ mod 17.
5. Find the last digit of 3¹⁰⁰ by spotting the cycle modulo 10.
6. Use Fermat’s little theorem to compute 4¹⁰⁰ mod 13.

Answers

1. 2⁵ = 32, 2¹⁰ = 32 × 32 = 1024 ≡ 24 (mod 1000).
2. 5² = 25 ≡ 12 ≡ −1 (mod 13), so 5⁶ = (5²)³ ≡ (−1)³ = −1 ≡ 12 (mod 13).
3. 23 in binary is 10111, so 23 = 16 + 4 + 2 + 1 and a²³ = a¹⁶ · a⁴ · a² · a¹.
4. 3² = 9, 3⁴ = 81 ≡ 13, 3⁸ ≡ 13² = 169 ≡ 16. Since 11 = 8 + 2 + 1, 3¹¹ ≡ 16 × 9 × 3 = 432 ≡ 7 (mod 17). Check: 432 = 17 × 25 + 7. ✓
5. The last digits of the powers of 3 run 3, 9, 7, 1 and repeat with period 4. Since 100 is a multiple of 4, the last digit of 3¹⁰⁰ is 1.
6. 13 is prime, so 4¹² ≡ 1 (mod 13). Since 100 = 12 × 8 + 4, 4¹⁰⁰ ≡ 4⁴ = 256 = 13 × 19 + 9 ≡ 9 (mod 13).

Modular Exponentiation FAQ

What is modular exponentiation?

It is the operation a^b mod n: raise a to the power b, then take the remainder on division by n. The point is that the answer can be reached without ever forming a^b, by reducing modulo n after every multiplication and by using repeated squaring to keep the multiplication count low.

How does repeated squaring work?

Squaring doubles the exponent for one multiplication, so a, a², a⁴, a⁸ and so on are cheap to build. Writing the target exponent in binary tells you which of those to multiply together. Exponent 13 is 1101 in binary, so a¹³ = a⁸ · a⁴ · a¹.

Why not just calculate the power and then take the remainder?

Because the intermediate value explodes. 7²²² has 188 digits, and a realistic cryptographic exponent produces a number with millions. Reducing at each step keeps every value below n², which stays small no matter how large the exponent is.

Can I reduce the exponent modulo n?

No, not modulo n. Exponents reduce modulo p − 1 for a prime modulus, by Fermat’s little theorem, or modulo φ(n) in general, by Euler’s theorem. Reducing the exponent by n itself gives a wrong answer.

How many multiplications does it take?

Roughly twice the number of binary digits in the exponent: one squaring per digit, plus one extra multiplication for each digit that is a 1. An exponent near a million needs about 26 multiplications instead of a million.

What is pow(a, b, n) in Python?

It is the built-in three argument form of pow, which performs modular exponentiation directly using this algorithm. pow(3, 45, 101) returns 32 immediately. Prefer it over 3 ** 45 % 101, which builds the full 22 digit power first.

Does this work with a negative exponent?

Only when a has a modular inverse. a⁻¹ mod n exists when gcd(a, n) = 1, and then a^(−k) means (a⁻¹)^k. Python’s pow supports this directly and raises an error when no inverse exists.

What is the connection between this and ordinary remainders?

Every step is an ordinary division with a remainder, of the kind described in how to find the remainder. Modular exponentiation is simply a schedule for arranging thousands of those steps so that the numbers never grow.