Modular Exponentiation Calculator

What Is Modular Exponentiation?

Modular exponentiation is the calculation of a^b mod m — raising a base a to an exponent b and keeping only the remainder when divided by modulus m. This operation is a cornerstone of modern number theory and public-key cryptography. No matter how large a and b are, the result is always an integer in the range [0, m−1].

For example, 3⁶⁴⁴ mod 645 = 36. While the intermediate value 3⁶⁴⁴ is an astronomically large number (over 300 decimal digits), the answer is simply 36.

Why Naive Computation Fails

The straightforward approach — compute a^b first, then take the remainder — is completely impractical for large exponents. The number 2¹⁰⁰⁰ already has over 300 decimal digits. RSA uses exponents with thousands of bits, so the naive intermediate value would have more digits than atoms in the observable universe. No computer could store it, let alone compute it.

The key insight is that we can reduce modulo m after every single multiplication, keeping all intermediate values below m². Combining this with the square-and-multiply trick reduces O(b) multiplications to O(log b).

The Square-and-Multiply (Binary Exponentiation) Algorithm

The algorithm processes the binary representation of b from LSB (least significant bit) to MSB. At step k (corresponding to bit k of b):

• Always square: compute base = base × base mod m (this accounts for the positional value 2^k)
• If bit k = 1: also multiply result = result × base mod m (include this power in the product)
• If bit k = 0: skip the multiplication (this power is not in the exponent)

The result accumulates only those powers of a whose corresponding bit in b is 1, exactly matching the binary decomposition b = ∑ b_k · 2^k.

O(log b) Complexity

The algorithm performs exactly ⌊log₂ b⌋ squarings and (popcount(b) − 1) multiplications, where popcount counts the number of 1-bits in b. Since both quantities are O(log b), the total number of modular multiplications is O(log b). Each multiplication involves numbers at most m² in size, requiring O((log m)²) bit operations. The overall bit complexity is O(log b × (log m)²).

For 2048-bit RSA parameters this means roughly 2000 multiplications of 2048-bit numbers — entirely feasible in milliseconds on any modern processor.

RSA Encryption and Decryption

RSA is the most widely deployed public-key cryptosystem. Key generation selects two large primes p and q, computes n = p × q, and chooses public exponent e coprime to φ(n) = (p−1)(q−1). The private exponent d = e⁻¹ mod φ(n) is computed by the Extended Euclidean Algorithm.

• Encryption: C = M^e mod n
• Decryption: M = C^d mod n

Both operations are pure modular exponentiation. The security of RSA depends on the fact that factoring n (and thus computing φ(n)) is computationally hard, even though encrypting and decrypting are fast.

Diffie-Hellman Key Exchange

Diffie-Hellman (1976) was the first practical public-key cryptographic protocol. Two parties agree publicly on a large prime p and a primitive root g. Each party selects a private random exponent and publishes their public value. The shared secret is g^ab mod p, computed by each party from the other's public value. An eavesdropper who sees both public values cannot compute the shared secret without solving the discrete logarithm problem — believed to be computationally hard for carefully chosen p and g.

Fermat's Little Theorem

Fermat's little theorem states: if p is prime and gcd(a, p) = 1, then a^p−1 ≡ 1 (mod p). This is a necessary condition for primality (though not sufficient — Carmichael numbers satisfy it for all bases while being composite). The Fermat primality test and the more reliable Miller-Rabin test both use modular exponentiation as their core computation.

Reference Table: Example Computations

a	b	m	ab mod m	b in binary	Squarings
3	644	645	36	1010000100	9
2	10	1000	24	1010	3
7	256	13	9	100000000	8
2	103	143	2	1100111	6
5	6	23	8	110	2
123	456	789	699	111001000	8