Why can’t we just compute a^b first and then take mod m?

For realistic cryptographic parameters, a^b is far too large to store or compute directly. Even for moderate sizes, a^b would overflow standard integer types. Modular exponentiation algorithms reduce modulo m after each multiplication, keeping intermediate values bounded and enabling computation for very large exponents.

How big can the numbers be in this calculator?

This calculator uses JavaScript BigInt, which supports arbitrarily large integers limited mainly by your device's memory and time. The exponent is processed in O(log b) time, so extremely large exponents are still feasible, but step-by-step output is automatically limited to keep the page responsive.

Why is modular exponentiation important in cryptography?

Public-key schemes such as RSA, Diffie–Hellman key exchange, and many digital signature algorithms rely on modular exponentiation with large integers. The security comes from problems like factoring and discrete logarithms, while the efficiency comes from fast modular exponentiation algorithms.

Modular Exponentiation Calculator

BigInt ready

Compute a^b mod m using fast binary exponentiation. Handles very large integers with JavaScript BigInt, and for smaller exponents shows the step-by-step square-and-multiply procedure used in programming contests and cryptography.

Perfect for number theory, competitive programming, and understanding how RSA and Diffie–Hellman use modular arithmetic in practice.

Fast a^b mod m calculator

Base a

Any integer (positive or negative). The calculator internally reduces it modulo m.

Exponent b

Non-negative integer exponent. Time complexity is O(log b).

Modulus m

Positive integer modulus (m ≥ 1). In many applications m is prime or a product of primes.

Show step-by-step square-and-multiply (for smaller exponents) Step view is auto-disabled if b has too many bits.

Quick examples

Result

Quantity	Value

Square-and-multiply steps (left-to-right binary exponentiation)

Step	Exponent bit	Result before	After squaring	After multiply (if bit=1)

What is modular exponentiation?

In modular arithmetic we work with integers modulo some positive integer \(m\). The expression \[ a^b \bmod m \] means that we first take the integer power \(a^b\) and then reduce it modulo \(m\) (i.e. take the remainder after division by \(m\)).

Naively, computing \(a^b\) and then reducing it is impossible for large \(b\): the intermediate result would have thousands of digits or more. Instead, modular exponentiation algorithms reduce modulo \(m\) at every step, keeping all intermediate values within the range \(\{0,\dots,m-1\}\).

Binary (square-and-multiply) algorithm

A standard way to compute \(a^b \bmod m\) is the binary exponentiation (or square-and-multiply) algorithm. Write the exponent \(b\) in binary:

\[ b = (b_{k-1}b_{k-2}\dots b_1 b_0)_2, \quad b_i \in \{0,1\}. \]

Then we process the bits from left to right:

\[ \text{result} \leftarrow 1 \] For each bit \(b_i\):
\( \quad \text{result} \leftarrow \text{result}^2 \bmod m\)
\( \quad \text{if } b_i = 1 \text{ then } \text{result} \leftarrow \text{result} \cdot a \bmod m \)

This uses O(\(\log b\)) multiplications, instead of \(b-1\) multiplications for the naive method. That is why it is the workhorse behind cryptographic schemes and competitive programming solutions.

Why modular exponentiation matters

Cryptography – RSA, Diffie–Hellman, ElGamal, and many signature schemes rely on computing \(a^b \bmod m\) for very large integers.
Number theory – tools like Fermat’s little theorem and Euler’s theorem use modular exponentiation to study structure in \(\mathbb{Z}_m\).
Programming – problems involving combinatorics “mod 10⁹+7” or “mod 998244353” are standard in contests; you almost never compute \(a^b\) directly.

Fast ab mod m calculator