Fast Modular Exponentiation Calculator
Compute b^e mod m using repeated squaring for cryptography and number theory. This educational calculator shows the formula, result, and step-by-step interpretation.
Calculator
What this calculator teaches
Fast modular exponentiation is used in RSA, Diffie-Hellman, digital signatures, and modular number theory.
Use the result as a learning aid. For classwork, still show the formula and intermediate reasoning so the final answer is not just a black-box number.
Why Repeated Squaring Is Fast
Fast modular exponentiation computes bᵉ mod m without ever constructing the potentially enormous number bᵉ. The key idea is to write the exponent in binary, square the base repeatedly, reduce after every multiplication, and multiply only the powers corresponding to 1-bits in the exponent.
For example, 13=8+4+1, so b¹³ can be assembled from b⁸·b⁴·b¹. Instead of performing 12 ordinary multiplications, repeated squaring needs only a logarithmic number of squaring and multiply steps. Modular reduction is valid throughout because products that are congruent modulo m remain congruent after multiplication.
| Idea | Rule |
|---|---|
| Reduce early | (ab) mod m = [(a mod m)(b mod m)] mod m |
| Square powers | b, b², b⁴, b⁸, … |
| Complexity | O(log e) multiplications |
This method is central to RSA, Diffie–Hellman, primality testing, and many number-theory algorithms. The modulus must be positive. Exponent 0 is valid and returns 1 mod m, so when m=1 the result is 0.
Sanity checks for modular powers. The final residue must lie between 0 and m−1 when m>0. If the base is already a multiple of m and the exponent is positive, the answer must be 0. If the base is congruent to 1 modulo m, every nonnegative power stays congruent to 1.
For small coprime examples, Euler's theorem offers another check: b^φ(m)≡1 (mod m) when gcd(b,m)=1. For prime modulus p and b not divisible by p, Fermat's little theorem gives b^(p−1)≡1 (mod p). These theorems can reduce an exponent before calculation, although repeated squaring works directly without requiring coprimality.
The binary representation of the exponent explains the algorithm directly. If e=13=1101₂, the selected powers are 8, 4, and 1. Repeated squaring produces b¹, b², b⁴, and b⁸ modulo m; multiplying the selected residues reconstructs b¹³ modulo m. This also makes the method convenient for computer implementations because each loop examines one bit of the exponent.
Formula & Symbols
| Concept | Formula or rule |
|---|---|
| Rule | b^e mod m |
| Repeated squaring | square and reduce after each binary digit |
Worked example
Common mistakes
Keep lists comma separated, matrices as rows separated by semicolons, and modular inputs as integers.
Some methods require positive probabilities, valid moduli, independent trials, or small educational input sizes.
Large powers overflow ordinary numeric types quickly. Reduce modulo m after each multiplication or squaring.
For positive modulus m, b⁰ mod m equals 1 mod m, even when b itself is large.
A final verification is to reduce the reported answer modulo m and confirm it stays in the expected residue range.
FAQ
Related calculators
These links will work after the calculators are registered in the final Math layout update.
Formula Explorer connections
Interpretation: This formula describes an algebraic relationship among variables, functions, equations, roots or sequences. Assumption: Respect the expression’s domain and excluded values. Check roots in the original equation because transformations can introduce extraneous solutions.