Modular Exponentiation Fast Power Calculator

Input Enter integers for base, exponent, and modulus.

Example data Click a row to load.

#	Base (a)	Exponent (b)	Modulus (m)	a^b mod m
1	5	117	19	1
2	4	13	497	445
3	7	560	561	1
4	2	1000	1009	942
5	123456789	12345	97	42

Result

Compute to see the result, steps, and chart.

Steps & Chart

#	Bit	Operation	Base	Result

Formula used

Goal: compute a^b mod m efficiently.

Binary (fast) exponentiation writes b in base two: b = \sum\_i 2^i. Repeatedly square and, when a bit is set, multiply the current result by the current base, always reducing modulo m. Complexity is O(log b) multiplications with modulus reductions.

// Pseudocode
res ← 1
x ← a mod m
while b > 0:
  if b is odd: res ← (res · x) mod m
  x ← (x · x) mod m
  b ← floor(b / 2)

How to use this calculator

Enter integers for Base a, Exponent b, and Modulus m.
Choose Method or leave Auto for best available precision.
Press Compute. The result, runtime, and step count will appear.
Review the table for each square and multiply operation.
Use Download buttons to export results CSV, steps CSV, or a PDF snapshot.

Example: Using Modular Exponentiation Fast Power

This worked example shows binary exponentiation on a=5, b=117, m=19.

Reduce base: x = a mod m = 5 mod 19 = 5.
Write exponent in binary: 117 = 1110101₂.
Scan bits from least significant to most significant, squaring each loop and multiplying when the bit is 1.

Loop	Bit	Operation	Base (x)	Result
1	1	multiply then square	5	5
2	0	square	6	5
3	1	multiply then square	17	9
4	0	square	4	9
5	1	multiply then square	16	11
6	1	multiply then square	9	4
7	1	multiply then square	5	1

Therefore, 5¹¹⁷ mod 19 = 1. You can load this example from the table and compare steps.

Applications and Domains

Public‑key cryptography (RSA, Diffie–Hellman, ElGamal).
Digital signatures and key exchange protocols.
Primality testing and residue classes.
Hashing schemes and commitment protocols.

Domain	Why it matters
RSA	Exponentiation under large moduli enables encryption and signatures.
DH/EC	Powers modulo m underpin shared secret derivation.
Blockchain	Residues and proofs rely on modular operations.

Complexity & Performance

Binary exponentiation uses O(log b) squarings and at most that many multiplies.

Exponent b	Bits	Iterations ≈
1,000	≈10	10
1,000,000	≈20	20
2⁴⁰	40	40
2²⁰⁴⁸	2048	2048

Tip: Using GMP accelerates large integer arithmetic; BCMath provides precise string math.

Edge Cases & Validation

Input	Condition	Behavior
m = 0	Invalid modulus	Error: modulus must be non‑zero.
b < 0	Negative exponent	Error: negative exponent unsupported.
a < 0	Negative base	Handled: reduced modulo m to [0, m).
a ≡ 0 (mod m)	Base multiple of m	Result is 0 unless b = 0.
b = 0	Zero exponent	Result is 1 for any m ≠ 0.

These cases are checked or handled in the calculator’s implementation.

Related Calculators