Modular Exponentiation Calculator — fast binary method

Modular exponentiation computes a^b mod n — the remainder when a raised to the power b is divided by n. Done naively it is impossible for the sizes that matter: raising 7 to the power 560 produces a number with 474 digits, and real cryptography uses exponents with hundreds of digits, giving results that would not fit in the observable universe. This modular exponentiation calculator uses binary exponentiation, also called repeated squaring, which finds the answer in a number of steps proportional to the number of bits in the exponent rather than to the exponent itself.

Arb Digital built the page around arbitrary-precision integers so that large inputs give correct answers rather than the silent floating-point corruption that most quick scripts produce past fifteen or sixteen digits. The step list shows each squaring and each multiplication, which is what turns the method from a black box into something you can reproduce on paper for small cases and trust for large ones.

What This Modular Exponentiation Calculator Does

It reads the base, the exponent and the modulus as whole numbers of any length, then works through the binary representation of the exponent from the most significant bit downward. At each bit the running result is squared and reduced modulo n; where the bit is a one, the result is also multiplied by the base and reduced again. After the last bit the running value is the answer.

The grid reports how many bits the exponent has, how many squarings and how many extra multiplications were needed, and how that compares with the naive approach of multiplying by a repeatedly. For an exponent of 560 the naive method needs 559 multiplications; the binary method needs about fifteen operations. For a 2,048-bit exponent the naive method needs more multiplications than there are atoms in the observable universe, and the binary method needs about three thousand.

This page is specifically about raising to a power under a modulus. Our modulo calculator handles the plain remainder operation with no exponent, and our modular inverse calculator finds the value that multiplies back to one, which is a different problem solved by a different algorithm.

How to Use It

1. Enter three whole numbers. The base may be negative, in which case it is reduced into the range 0 to n − 1 before anything else happens.
2. Use as large an exponent as you like. The calculation is done in arbitrary-precision integers, so a hundred-digit exponent is no slower to a human eye than a three-digit one.
3. Keep the modulus above zero. A modulus of zero has no meaningful remainder, and a modulus of one always gives zero, since everything is divisible by one.
4. Read the step list for small cases. Working through a short exponent by hand alongside the list is the fastest way to internalise the method.
5. Check the operation comparison. It shows concretely why this algorithm exists, and the gap widens dramatically as the exponent grows.

The Method and How It's Calculated

Take 3¹³ mod 17 by hand. Write 13 in binary as 1101, meaning 13 = 8 + 4 + 1. Build the powers of 3 by squaring: 3¹ = 3, 3² = 9, 3⁴ = 81 which is 13 mod 17, and 3⁸ = 13² = 169 which is 16 mod 17. Now multiply the ones you need: 16 × 13 × 3 = 624, and 624 mod 17 = 12. So 3¹³ mod 17 = 12, which you can confirm directly since 3¹³ is 1,594,323 and dividing by 17 leaves remainder 12.

The left-to-right version the calculator uses reaches the same place with less storage. Start with 1 and read the bits of 13 — that is 1, 1, 0, 1 — from the left. Square then multiply for a one bit, square only for a zero bit. Starting from 1: square to 1, multiply by 3 giving 3; square to 9, multiply by 3 giving 27 ≡ 10; square 10 to 100 ≡ 15; square 15 to 225 ≡ 4, multiply by 3 giving 12. Same answer, and nothing larger than 225 ever appeared.

That bound is the key property. Since every intermediate is reduced modulo n before the next step, the largest number the algorithm ever holds is roughly n². With a 2,048-bit modulus that means 4,096-bit intermediates, which is entirely routine, whereas a^b without reduction would have more digits than could be written down. Repeated squaring and its cost analysis are covered in the number theory unit of the MIT OpenCourseWare Mathematics for Computer Science course.

Why the Cost Is Logarithmic

The naive approach multiplies by a once for each unit of the exponent, so the cost is b operations. Binary exponentiation performs one squaring per bit of b, plus one extra multiplication for each bit that is a one. The number of bits in b is about log₂ b, so the total is at most 2 log₂ b operations — twice the bit length in the worst case, and about 1.5 times on average since roughly half the bits are ones.

The difference is not a constant factor but a change in category. Doubling the exponent adds one operation instead of doubling the total. An exponent of a million needs about thirty operations. An exponent of 2¹⁰⁰⁰ needs about two thousand. That is the difference between a computation that finishes instantly and one that never finishes at all, and it is why public key cryptography is possible.

Each individual operation is not free, of course. Multiplying two n-bit numbers costs more than multiplying two small ones, and reducing modulo n costs a division. So the real cost is the operation count multiplied by the cost of arithmetic at that size, which is why key sizes have real performance consequences even though the algorithm is logarithmic in the exponent.

Where This Is Used

RSA encryption and decryption are both a single modular exponentiation. Encrypting a message m means computing m^e mod n with the public exponent, and decrypting means computing c^d mod n with the private one. The security rests on the fact that recovering d from the public information requires factoring n, while the exponentiation itself is cheap in both directions. Diffie-Hellman key exchange is the same operation used differently: each party computes g^x mod p, exchanges the result, and exponentiates again.

Primality testing is the other major use. The Fermat test checks whether aⁿ⁻¹ ≡ 1 mod n, which must hold when n is prime. The default values in this tool are a deliberate counterexample: 7⁵⁶⁰ mod 561 equals 1, yet 561 = 3 × 11 × 17 is composite. Numbers that pass the Fermat test for every base coprime to them are called Carmichael numbers, and 561 is the smallest. Our prime number checker uses stronger tests that Carmichael numbers do not fool, and our prime factorization calculator finds the factors directly.

Hash-based and signature schemes lean on the same primitive. The digital signature standard specifies modular exponentiation in its discrete-logarithm-based algorithms, and the parameter sizes there are chosen precisely because the exponentiation is easy while its inverse — the discrete logarithm — is not. The current specification is NIST FIPS 186-5, the Digital Signature Standard.

Reducing the Exponent Before You Start

Sometimes the exponent can be shrunk before any squaring happens. Fermat's little theorem says that if p is prime and a is not divisible by p, then a^p−1 ≡ 1 mod p. So exponents can be reduced modulo p − 1: computing 3¹⁰⁰⁰ mod 7 becomes 3^{1000 mod 6} = 3⁴ = 81 ≡ 4 mod 7, with no large exponent at all.

Euler's theorem generalises this to composite moduli: a^φ(n) ≡ 1 mod n whenever a and n share no common factor, where φ(n) counts the integers below n that are coprime to it. This is exactly the fact that makes RSA decryption work, since the private exponent is chosen as the inverse of the public one modulo φ(n).

The condition is easy to forget and the failure is silent. Both theorems require gcd(a, n) = 1. Apply the reduction when the base shares a factor with the modulus and you get a plausible wrong answer rather than an error. Checking the greatest common divisor first is the safeguard, and our modular inverse calculator reports that gcd as part of its output.

Negative Exponents and Other Edge Cases

An exponent of zero gives 1 for any base, with the single exception of a modulus of 1, where every value is congruent to 0. A base of zero gives 0 for any positive exponent. A base that is a multiple of the modulus behaves the same way, since it is congruent to zero.

Negative exponents are not simply undefined; they mean something specific. a⁻¹ mod n is the modular inverse of a, so a^−k mod n is the inverse raised to the k. It exists only when a and n are coprime, which is why this tool asks for a non-negative exponent and points you to the inverse calculator instead of guessing.

Negative bases are handled by reduction. Since −4 and n − 4 are congruent modulo n, the calculator replaces a negative base by its non-negative representative before starting, which keeps every intermediate value in the range 0 to n − 1. That is a convention rather than a mathematical necessity — some systems return negative remainders — but it is the convention used almost everywhere in number theory, and the same one applied on our modulo calculator.

Common Mistakes to Avoid

• Computing the power first and reducing at the end — the intermediate number overflows any fixed-size type long before the exponent gets interesting.
• Using floating-point arithmetic — doubles lose exactness past about sixteen digits, and a modular result that is off by one is simply wrong with no warning.
• Applying Fermat's little theorem without checking the gcd — the reduction of the exponent is valid only when the base and modulus are coprime.
• Treating a Fermat test pass as proof of primality — Carmichael numbers such as 561 pass for every coprime base while being composite.
• Feeding a negative exponent to a power routine — it means the modular inverse raised to that power, which needs a different algorithm and may not exist at all.

Related Free Tools From Arb Digital

Take a plain remainder with the modulo calculator, find the value that multiplies back to one with the modular inverse calculator, test a number for primality with the prime number checker, split it into factors with the prime factorization calculator, or convert the exponent into binary with the number base converter. The full free online tools hub lists every mathematics tool we publish.

Frequently Asked Questions

This page explains a mathematical method for study and for checking your own working. It is not a substitute for showing your method, and it is not medical, legal, or financial advice.