Modular Exponentiation Calculator

Compute a Power Modulo m

Modular Exponentiation Formula

Formula

\[ c \;=\; b^e \bmod m \] \[ e = \sum_{k=0}^{n} e_k\,2^k \;\;\Longrightarrow\;\; b^e \;\equiv\; \prod_{k:\; e_k = 1} \bigl(b^{2^k} \bmod m\bigr) \pmod{m}, \qquad b^{2^k} \equiv \bigl(b^{2^{k-1}}\bigr)^2 \pmod{m} \]

Where:

\(b\) — the base (any whole number)
\(e\) — the exponent (a non-negative whole number)
\(m\) — the modulus (a positive whole number)
\(e_k\) — the bits of \(e\) in its binary expansion
\(c\) — the result: the remainder of \(b^e\) upon division by \(m\)

The first line defines modular exponentiation. The second line is the square-and-multiply (binary exponentiation) identity the calculator uses: the exponent is decomposed into powers of two, the powers \(b^{2^k}\) are found by repeated squaring, and only the ones matching set bits are multiplied together — all modulo \(m\), so the intermediate numbers never explode.

Modular Exponentiation – Calculation Example

Example: compute \(3^{644} \bmod 645\), the calculator's default values. The integer \(3^{644}\) has 308 digits, so evaluating the power first and reducing afterwards is hopeless.

Step 1 — reduce the base: \(3 \bmod 645 = 3\).

Step 2 — write the exponent in binary:

\[ 644 = 512 + 128 + 4 = 1010000100_2 \]

Repeated squaring modulo 645 gives \(3^4 \equiv 81\), \(3^{128} \equiv 396\) and \(3^{512} \equiv 111 \pmod{645}\) for the set bits.

Step 3 — multiply those values, reducing mod 645 each time:

\[ 3^{644} \equiv 81 \times 396 \times 111 \equiv 471 \times 111 \equiv 52281 \equiv 36 \pmod{645} \]

Result: \(3^{644} \bmod 645 = 36\). The algorithm needed only 9 squarings and 3 multiplications — 12 modular operations instead of the 643 a naive approach would require.

How to Use the Calculator

Enter the Base (b) — any whole number, positive or negative.
Enter the Exponent (e) — a non-negative whole number. It may be far too large for \(b^e\) to be computed directly; that is exactly what this tool is for.
Enter the Modulus (m) — any positive whole number.
Leave Show repeated-squaring steps ticked if you want the binary expansion of the exponent and a table of every squaring step; untick it for a plain answer.
Read Result (bᵉ mod m), the Reduced base (b mod m), and the step-by-step breakdown.

What Is Modular Exponentiation?

Modular exponentiation answers the question: what is the remainder when \(b^e\) is divided by \(m\)? The result always lies between \(0\) and \(m-1\). Equivalently, it is the number \(c\) with \(0 \le c < m\) such that \(b^e \equiv c \pmod{m}\). For example, \(3^{644} \bmod 645 = 36\) means \(3^{644}\) leaves a remainder of 36 when divided by 645.

The naive way — computing \(b^e\) and then taking the remainder — fails quickly. \(3^{644}\) already has 308 digits, and cryptographic applications routinely use exponents with hundreds of digits, where \(b^e\) would have more digits than there are atoms in the universe. The fix is the square-and-multiply method: write the exponent in binary, obtain \(b^{2^k} \bmod m\) by repeatedly squaring and reducing, then multiply together only the values corresponding to set bits. This needs just \(O(\log e)\) modular multiplications instead of \(e-1\), and because every intermediate result is reduced modulo \(m\), no number ever grows beyond roughly \(m^2\).

Modular exponentiation is the workhorse of public-key cryptography. RSA encryption and decryption are a single modular exponentiation with a huge modulus; Diffie–Hellman key exchange and the ElGamal scheme rely on it too. It also powers primality tests such as the Fermat and Miller–Rabin tests, which check whether \(a^{n-1} \equiv 1 \pmod n\) — you can explore the underlying number theory with our Fermat's Little Theorem and Euler's Theorem calculators.

The step display makes the algorithm transparent: the table lists every bit position \(k\) of the exponent next to \(b^{2^k} \bmod m\), the bold rows are the ones actually used, and their product (reduced mod \(m\)) is your answer. This is precisely what computer algebra systems do internally, and seeing it once is the best way to understand why huge exponents are cheap.

Assumptions, Limits and Tips

Exponent must be non-negative. A negative exponent would require the modular inverse of \(b\), which exists only when \(\gcd(b, m) = 1\). To handle that case, first find the inverse with our Multiplicative Inverse Modulo calculator and then use its output as the base with a positive exponent.
Modulus must be positive. If \(m = 1\), every integer is congruent to 0, so the result is 0 — that is mathematically correct, not an error.
Negative bases are fine. The base is first reduced to its least non-negative residue \(b \bmod m\), so \(-12\) and \(m - 12\) give the same answer.
Exponent 0 gives \(1 \bmod m\) (which is 0 only when \(m = 1\)), consistent with \(b^0 = 1\).
Size limits: the base and modulus may each have up to 1000 digits, and the exponent may be as large as \(10^{18}\). Since the algorithm is logarithmic in the exponent, even that runs instantly.
Check answers with a different route: for a composite modulus you can split the computation into prime-power pieces and recombine them — try our Chinese Remainder Theorem calculator to verify results independently.

Frequently Asked Questions

How do I compute a power mod m by hand?

Use the square-and-multiply method. First reduce the base: replace b with \(b \bmod m\). Then write the exponent in binary and repeatedly square the base, reducing modulo m after each step: \(b^2, b^4, b^8, b^{16}, \ldots\). Finally multiply together only the squared values that correspond to the 1-bits of the exponent, reducing mod m each time. This keeps every intermediate number below \(m^2\).

Why is the result of b^e mod m always between 0 and m-1?

Because modular arithmetic works with least non-negative residues. The expression \(b^e \bmod m\) is defined as the remainder when \(b^e\) is divided by \(m\), and division remainders always satisfy \(0 \le c \le m-1\). Even if the base is negative, it is first converted to its equivalent positive residue, so the answer is never negative.

What is the last digit of a large power (like 7^100)?

That is a modular exponentiation in disguise: the last digit of a number is that number mod 10. So compute \(7^{100} \bmod 10\) here. Similarly, the last two digits are the value mod 100, and the last three digits are the value mod 1000. This is a classic shortcut for olympiad and homework problems about final digits.

What happens if the exponent is 0 or the modulus is 1?

With \(e = 0\) the result is \(1 \bmod m\), which equals 1 for every modulus except \(m = 1\), where it equals 0 — since every integer is congruent to 0 modulo 1. These edge cases are handled correctly, and \(m = 1\) always returns 0 for any base and exponent, which is mathematically right rather than an error.

Can I use a negative base or a negative exponent?

Negative bases are fine: the calculator reduces them to an equivalent positive residue first, so \(-12\) behaves like \(m - 12\). Negative exponents are not supported, because they would require the modular inverse of the base, which exists only when \(\gcd(b, m) = 1\). Work around it by finding \(b^{-1} \bmod m\) first, then raising that to the power \(|e|\).

How is modular exponentiation used in RSA and cryptography?

RSA encryption and decryption are each a single modular exponentiation \(c = m^e \bmod n\) with a modulus of 2048+ bits, which is exactly what square-and-multiply computes efficiently. Diffie–Hellman key exchange and ElGamal work the same way. The method's \(O(\log e)\) speed makes huge exponents feasible, while the difficulty of reversing the operation without the secret key keeps the schemes secure.

What is a common mistake when computing b^e mod m?

The most common error is computing \(b^e\) first and taking the remainder afterwards — the power quickly becomes astronomically large and either overflows a calculator or is impossible to write down. Always reduce modulo m after every squaring and multiplication instead. Another frequent slip is forgetting that \(b^0 \bmod 1 = 0\), not 1, because everything is congruent to 0 modulo 1.