Compute ab mod n for very large numbers with the square-and-multiply algorithm, with the binary breakdown of the exponent and a step table.
Computing ab first and reducing afterwards is hopeless for cryptographic sizes: 7560 already has 474 digits, and RSA exponents are hundreds of digits long. Modular exponentiation avoids this by reducing modulo n after every multiplication, so the numbers never grow beyond n².
Write the exponent b in binary. Start with r = 1 and read the bits from the most significant to the least significant. For each bit, first square the running result, r ← r² mod n; then, if the bit is 1, also multiply by the base, r ← r·a mod n. After the last bit, r equals ab mod n.
The method needs only about log₂(b) squarings and at most as many multiplications, so even a 2048-bit exponent needs only a few thousand modular multiplications. The table in this calculator lists each bit, the square, the optional multiplication and the running value.
RSA encryption and decryption are modular exponentiations (c = me mod n and m = cd mod n). Diffie–Hellman and ElGamal compute powers modulo a prime, and primality tests such as Fermat and Miller–Rabin depend on them. A classic check: for the Carmichael number 561, 7560 ≡ 1 (mod 561) even though 561 = 3·11·17 is not prime.
The base may be negative; it is first reduced to its residue modulo n. The exponent must be a non-negative integer and the modulus a positive integer. If n = 1 every result is 0, and any non-zero base with exponent 0 gives 1 mod n.
A worked mini example: to compute 313 mod 7, write 13 = 1101 in binary. Start with r = 1. Bit 1: square (1) then multiply by 3 to get 3. Bit 1: square to 9 ≡ 2, multiply by 3 to get 6. Bit 0: square to 36 ≡ 1. Bit 1: square to 1, multiply by 3 to get 3. So 313 ≡ 3 (mod 7), which agrees with Fermat's little theorem because 36 ≡ 1 (mod 7) and 13 = 2·6 + 1.
These examples are computed by the same engine as the calculator above, so you can compare each step with your own working.
| Position | Bit | Square | Multiply | r |
|---|---|---|---|---|
| 9 | 1 | 1 | 7 | 7 |
| 8 | 0 | 49 | — | 49 |
| 7 | 0 | 157 | — | 157 |
| 6 | 0 | 526 | — | 526 |
| 5 | 1 | 103 | 160 | 160 |
| 4 | 1 | 355 | 241 | 241 |
| 3 | 0 | 298 | — | 298 |
| 2 | 0 | 166 | — | 166 |
| 1 | 0 | 67 | — | 67 |
| 0 | 0 | 1 | — | 1 |
| Position | Bit | Square | Multiply | r |
|---|---|---|---|---|
| 7 | 1 | 1 | 3 | 3 |
| 6 | 1 | 9 | 27 | 27 |
| 5 | 0 | 29 | — | 29 |
| 4 | 0 | 41 | — | 41 |
| 3 | 1 | 31 | 43 | 43 |
| 2 | 0 | 49 | — | 49 |
| 1 | 0 | 1 | — | 1 |
| 0 | 0 | 1 | — | 1 |
It needs about log₂(b) squarings and at most the same number of multiplications, so the cost grows with the number of bits of the exponent, not with the exponent itself.
Write b in binary, then for each bit from the left square the running value and, when the bit is 1, multiply by a, reducing modulo n each time. The table in this tool follows exactly that procedure.
Not in this calculator. A negative exponent means a modular inverse followed by a power; compute the inverse with the extended Euclidean tool first.
561 is a Carmichael number, a composite number that satisfies a^(n−1) ≡ 1 (mod n) for every a coprime to it. It is the smallest such number.
Generate an RSA key pair from two primes and encrypt or decrypt an integer, with every calculation shown.
Walk through a Diffie–Hellman key exchange: public values, shared secret and a check that both sides agree.
Find gcd(a, b), Bézout coefficients and modular inverses, with the full quotient / remainder table.
Find the smallest primitive root modulo n, count them, list them and test whether a given g generates the group.