How Power Mod (Modular Exponentiation) Works
Power mod computes ab mod m — raise a base a to an exponent b, then keep only the remainder after dividing by a modulus m. The result is always a whole number between 0 and m-1. Computing this directly by first raising a to the power b is impractical for anything but tiny exponents, since ab grows explosively (2313 already has 18 digits). This calculator instead uses modular exponentiation via the square-and-multiply algorithm, which reduces modulo m after every multiplication so the numbers involved never grow larger than roughly m².
Formula and method: square-and-multiply
The fast algorithm writes the exponent b in binary and processes it one bit at a time, from least significant to most significant. Start with result = 1 and reduce the base modulo m. For each bit: if the bit is 1, multiply the running result by the current base (mod m); then always square the current base (mod m) and move to the next bit. This performs about 2·log2(b) modular multiplications total — for b = 13 (binary 1101) that is only 7 multiplications instead of the 12 a naive "multiply a by itself b-1 times" approach would need, and the gap widens dramatically as b grows.
Worked example
To compute 2313 mod 17: first reduce the base, 23 mod 17 = 6. Write 13 in binary as 1101. Processing the bits gives intermediate results of 6, then 7, then 10 — so 2313 mod 17 = 10. You can verify this with a much smaller check: 23 mod 5 = 8 mod 5 = 3, since 8 = 1×5 + 3.
Common sources of error
- Computing the full power first: for larger exponents this produces enormous intermediate numbers and can silently overflow fixed-precision arithmetic in some tools — always reduce modulo m at every step, not just at the end.
- Negative exponents: a-b mod m requires the modular inverse of a (via the extended Euclidean algorithm), which only exists when a and m are coprime; this calculator accepts non-negative integer exponents only.
- Modulus of 0 or a non-integer: the modulus must be a positive integer (m ≥ 1); "mod 0" is undefined, and a modulus of 1 always yields a result of 0.
Applications
Modular exponentiation is the workhorse operation behind RSA and Diffie-Hellman public-key cryptography, digital signatures, and the Miller-Rabin and Fermat primality tests. It also appears in hash functions, checksums, and pseudorandom number generators, and is a standard building block in competitive programming and number theory coursework whenever a result must stay within a fixed-size range.