Modular Exponentiation in Python: pow(b, e, n) Explained

Modular exponentiation computes b**e % n without overflow and is the core arithmetic primitive inside RSA encryption.

It shows up in placement coding problems under several labels: “encrypt a message with two keys”, “compute a large power modulo a prime”, “fast exponentiation”. Every variant reduces to the same algorithm. This article covers the math, the overflow problem, the algorithm, Python’s built-in shortcut, and the two-step compound formula that appears in competitive programming problems.

What the formula means

The core operation is:

encrypted = (message ** e) % n

Raise the message to the power e, then take the remainder when dividing by n. The result always falls in the range 0 to n - 1.

In RSA, e is the public exponent (65537 by convention in production implementations) and n is the product of two large primes. Placement problems skip key-pair generation and give you e and n directly. You just compute the formula.

A concrete worked example, verified from first principles:

• Message = 7, exponent e = 5, modulus n = 11
• Naive calculation: 7**5 = 16807
• Remainder check: 11 * 1527 = 16797; 16807 - 16797 = 10
• Encrypted value: 10

Small numbers make this painless. The problem begins when e and n reach the range typical in placement coding problems: both can go up to 10^10.

Why naive exponentiation fails

The Python expression b**e % n evaluates left to right: Python first computes the full value of b**e, then applies % n. For small inputs that is fine. For b = 123456789 and e = 10000000000, the intermediate number has roughly ninety billion digits.

Python’s arbitrary-precision integers will eventually compute it without crashing. In practice, on a placement platform or online judge with a 1-2 second time limit and 256 MB memory cap, it times out or runs out of memory before finishing.

pow(b, e) % n has the same problem: Python evaluates pow(b, e) as the full integer before applying % n.

The fix: reduce by the modulus at every multiplication step, keeping intermediate values bounded throughout.

The square-and-multiply algorithm

The key property: (a * b) % n == ((a % n) * (b % n)) % n.

Multiplying modular residues gives the same result as multiplying first and reducing after. This means you can insert a % n after every multiplication without changing the final answer.

The square-and-multiply algorithm (also called binary exponentiation or fast modular exponentiation) applies this reduction at each step:

def mod_exp(base, exp, mod):
    result = 1
    base = base % mod       # reduce base before starting
    while exp > 0:
        if exp % 2 == 1:    # current bit of exponent is 1
            result = (result * base) % mod
        exp = exp // 2      # shift right through the exponent bits
        base = (base * base) % mod   # square the base
    return result

The loop runs at most log2(exp) iterations. For exp = 10^10, that is about 33 iterations instead of ten billion.

Traced step by step: mod_exp(7, 5, 11)

• Initial state: result = 1, base = 7 % 11 = 7, exp = 5
• Step 1: exp = 5 (odd) → result = (1 * 7) % 11 = 7; exp = 5 // 2 = 2; base = (7 * 7) % 11 = 49 % 11 = 5
• Step 2: exp = 2 (even) → result stays 7; exp = 2 // 2 = 1; base = (5 * 5) % 11 = 25 % 11 = 3
• Step 3: exp = 1 (odd) → result = (7 * 3) % 11 = 21 % 11 = 10; exp = 1 // 2 = 0
• exp = 0, loop ends. Return 10 ✓

Three iterations instead of four multiplications. For large exponents the ratio grows as log2(exp).

Python’s three-argument pow()

Python’s standard built-in already implements this algorithm. Pass the modulus as the third argument:

result = pow(7, 5, 11)    # returns 10

The Python 3 documentation for pow() states that when the three-argument form is used, intermediate values never grow larger than mod * mod, regardless of the size of exp. This keeps memory use constant throughout. It is the idiomatic Python solution.

Use pow(b, e, n) when you need the result inside a larger program. Write the manual mod_exp function when the question explicitly asks you to implement the algorithm. Placement questions usually accept either, but competitive programming problems with large inputs will time out if you accidentally use the two-argument form.

The two-step nested formula

The compound placement problem uses this formula:

encrypted = ((S^N % 10)^M) % 1000000007

Where:

• S is the secret code (up to 10^9)
• N and M are key values (up to 10^10)
• 1000000007 (10^9 + 7) is a standard large prime used in competitive programming to keep results in range

Decompose it into two calls to pow():

def encrypt_code(S, N, M):
    step1 = pow(S, N, 10)                  # last digit of S^N
    result = pow(step1, M, 1000000007)
    return result

# Verified example: S=123456789, N=10000000000, M=10000000000
# step1: last digit of 123456789 is 9; powers of 9 mod 10 have period 2
#        (9, 1, 9, 1, ...); N is even so pow(123456789, 10000000000, 10) = 1
# result: pow(1, 10000000000, 1000000007) = 1
print(encrypt_code(123456789, 10000000000, 10000000000))  # Output: 1

Each call handles its own modulus independently. Neither call ever produces an intermediate value larger than its modulus squared.

Common mistakes in this problem type

• Confusing public key with shared secret. RSA encryption uses the public exponent e and modulus n. Placement problems give these directly. Do not add key-generation logic the problem does not ask for.
• Non-coprime modulus. For valid RSA-style problems, gcd(message, n) should equal 1. A message that shares a factor with n produces an encryption that cannot be reversed. Check that message < n.
• Applying mod only at the end. pow(b, e) % n computes the full power first. For large exponents, use pow(b, e, n) or the manual mod_exp loop.

Time and space complexity

Approach	Multiplications	Space	Valid for e up to 10^10
Naive b**e % n	O(e)	O(e log b) bits	No — ten billion operations
mod_exp (square-and-multiply)	O(log e)	O(log b) bits	Yes — ~33 iterations
pow(b, e, n)	O(log e)	O(log n) bits	Yes — same algorithm

For competitive programming and placement tests, O(log e) is the required complexity. Any O(e) approach will time out on inputs with e near 10^10.

The Armstrong number problem in the Python power-based programs guide uses ** for small fixed exponents (at most 3 or 4 digits) where overflow is not a concern. Modular exponentiation extends that same operator to arbitrarily large exponents by reducing at each step. Both patterns appear in placement coding rounds at TCS, Infosys, and Wipro; the Python basic programs collection covers the full pattern set.

pow(b, e, n) compresses a 33-iteration algorithm into one readable line. The same compression logic appears in the Python calculator program when guarding division: one conditional check replaces the entire error branch. Building LLM-powered applications involves this same layered arithmetic: JWT token signing and HMAC key derivation both use modular exponentiation on every authenticated API request. TinkerLLM’s hands-on LLM playground at ₹299 puts those real API calls in your hands; understanding pow(b, e, n) is the foundation that makes debugging authentication failures much faster.