Power Mod Calculator (Modular Exponentiation)
Enter a base, exponent, and modulus to compute modular exponentiation (a^b mod n). The calculator uses the binary square-and-multiply algorithm so it handles very large exponents in milliseconds without overflow. The step-by-step panel shows the full binary table, and the reference section covers Fermat's Little Theorem, Euler's theorem, and common use cases in cryptography.
What is modular exponentiation?
Modular exponentiation computes a^b mod n: raise a base (a) to an exponent (b), then find the remainder when divided by a modulus (n). The result is always a non-negative integer between 0 and n-1. For small numbers you could compute a^b first and then divide, but when b is even modestly large the intermediate number becomes astronomically big. A 2048-bit RSA key, for example, involves exponents with hundreds of digits. The binary square-and-multiply algorithm solves this by keeping every intermediate result reduced modulo n, so the numbers never grow beyond n^2 in size, regardless of how large b is.
How the binary square-and-multiply algorithm works
Write the exponent b in binary. The algorithm starts with c = 1 and scans the bits from the most significant to the least significant. For each bit it squares c (mod n). If the bit is 1, it additionally multiplies c by the base (mod n). After processing all bits, c holds the final answer. For example, 3^17 mod 25: 17 in binary is 10001. Starting from c = 3, the steps produce 9, 6, 11, 13, and finally 13. The full table is shown in the "Show Your Work" panel above. The algorithm performs at most 2 * floor(log2(b)) multiplications, so even a 1000-bit exponent needs only about 2000 operations rather than 2^1000.
Fermat's Little Theorem and why it matters
Fermat's Little Theorem states that when n is prime and a is not a multiple of n, a^(n-1) mod n = 1. This means the powers of a cycle with period dividing n-1, so you can reduce a large exponent: a^b mod n = a^(b mod (n-1)) mod n. For instance, 2^100 mod 7: since 7 is prime, reduce the exponent: 100 mod 6 = 4, so the answer is 2^4 mod 7 = 16 mod 7 = 2. Euler's more general theorem extends this to composite moduli using Euler's totient function phi(n), but computing phi(n) itself requires knowing the prime factorisation of n, which is computationally hard for large n - and that hardness is the foundation of RSA.
Applications in cryptography and number theory
Modular exponentiation is the central operation in public-key cryptography. RSA encryption computes ciphertext = plaintext^e mod N, where (e, N) is the public key. Decryption computes plaintext = ciphertext^d mod N using the private exponent d. Diffie-Hellman key exchange is built on g^a mod p, and digital signatures (DSA, ECDSA) rely on the same operation. The Miller-Rabin primality test checks whether a^(n-1) mod n = 1 for several random bases a to decide if n is probably prime. Discrete logarithm problems - finding b such that a^b mod n = c - are hard to solve, and that asymmetry (computing a^b mod n is easy, reversing it is hard) secures most of the internet's encryption.
Key theorems and special cases
| Condition | Identity | Example |
|---|---|---|
| n = 1 | a^b mod 1 = 0 (always) | 999^999 mod 1 = 0 |
| b = 0 | a^0 mod n = 1 (for n > 1) | 7^0 mod 13 = 1 |
| b = 1 | a^1 mod n = a mod n | 17^1 mod 5 = 2 |
| n prime, gcd(a,n)=1 | a^(n-1) mod n = 1 (Fermat) | 2^6 mod 7 = 1 |
| n prime, gcd(a,n)=1 | a^b mod n = a^(b mod n-1) mod n | 2^100 mod 7 = 2^(100 mod 6) mod 7 |
| Euler's theorem | a^phi(n) mod n = 1, gcd(a,n)=1 | 3^4 mod 5 = 1 (phi(5)=4) |
| a = 0 | 0^b mod n = 0 (b > 0) | 0^100 mod 7 = 0 |
| a = 1 | 1^b mod n = 1 | 1^1000 mod 17 = 1 |
These identities let you simplify modular exponentiation before computing.
Frequently asked questions
What is a power mod calculation?
A power mod (modular exponentiation) calculation finds the remainder of a^b (a raised to the power b) when divided by n. Written as a^b mod n, it always returns a non-negative integer between 0 and n-1. For example, 3^4 mod 5 = 81 mod 5 = 1.
Why not just compute a^b and then take the modulus?
For small numbers that works fine, but exponents in cryptography are hundreds or thousands of digits long. Computing a^b first would produce a number with millions of digits, which is impractical even for a computer. The binary square-and-multiply algorithm avoids this by reducing mod n at every step, keeping all intermediate values small.
How does the binary square-and-multiply algorithm work?
Write the exponent in binary. Scan the bits left to right, starting with c = a mod n after the first (leading) bit. For each subsequent bit: square c (mod n). If the bit is 1, also multiply by a (mod n). After all bits are processed, c is the answer. This needs at most 2 * log2(b) multiplications instead of b multiplications.
What does Fermat's Little Theorem say about power mod?
When n is prime and gcd(a, n) = 1, Fermat's Little Theorem guarantees a^(n-1) mod n = 1. A practical consequence is that a^b mod n = a^(b mod (n-1)) mod n, so you can reduce a huge exponent before computing. This does not work when n is composite; use Euler's theorem (a^phi(n) mod n = 1) in that case.
Can the base be negative?
Yes. A negative base is normalised by adding multiples of n until it is in the range [0, n-1] before computation begins. For example, (-3)^2 mod 7: normalise -3 to 4 (mod 7), then 4^2 mod 7 = 16 mod 7 = 2. This calculator performs that normalisation automatically.
What happens when the modulus is 1?
Any integer modulo 1 is 0, so a^b mod 1 = 0 for all values of a and b. This is a degenerate case since there is only one residue class.
Where is modular exponentiation used in practice?
RSA public-key encryption, Diffie-Hellman key exchange, digital signature algorithms (DSA, ECDSA), Miller-Rabin primality testing, and generating pseudo-random numbers in linear congruential generators all use modular exponentiation as their core operation.