What this calculator does
Raising a number to a large power and taking the remainder sounds like it needs an enormous intermediate value. Square-and-multiply avoids that entirely by reducing modulo m at every step, so the numbers never grow.
It is also dramatically faster. Computing 4 to the power 13 modulo 497 takes four squarings rather than twelve multiplications, and the advantage grows enormously for the exponents cryptography actually uses.
The formula
The exponent is processed bit by bit. The base is repeatedly squared, and the running result is multiplied by it whenever the current bit is 1, with a reduction modulo m after every operation.
| Term | Meaning |
|---|---|
| Square-and-multiply | The algorithm that makes large modular powers tractable. |
| Modular reduction | Taking the remainder at every step, which keeps the numbers small. |
| Logarithmic time | The work grows with the number of bits in the exponent, not its size. |
The inputs explained
| Field | What to enter |
|---|---|
| Base | The base to raise. |
| Exponent (non-negative integer) | The exponent. Must be non-negative. |
| Modulus | The modulus, at least 1. |
When to use it
RSA encryption
Both encryption and decryption are modular exponentiations.
Diffie-Hellman key exchange
The entire protocol rests on this operation being fast.
Primality testing
Fermat and Miller-Rabin tests both require modular powers.
Worked examples
Every figure in the tables below is produced by this page’s own calculator at build time, so the numbers and the tool always agree. Select any row to load that scenario.
How does the exponent affect the work?
Three exponents with the same base and modulus.
Questions
Why not just compute the power then take the remainder?
Because the intermediate value would be astronomically large. RSA uses exponents of hundreds of digits, and the full power would have more digits than there are atoms in the observable universe.
How does reducing at each step stay correct?
Because modular arithmetic is compatible with multiplication: the remainder of a product equals the product of the remainders, reduced again. That property is what lets the intermediate values stay small.
How much faster is it?
Enormously. An exponent of n requires roughly log base 2 of n squarings rather than n multiplications. For a 2048-bit exponent that is about 2,000 operations instead of a number with 600 digits.
Is the straightforward version secure?
Not against timing attacks. The basic algorithm takes different paths depending on the exponent bits, which leaks information through timing. Cryptographic implementations use constant-time variants for that reason.
For modular inverses, see the modular inverse calculator. For simultaneous congruences, see the Chinese remainder theorem calculator.