Modular Exponentiation Calculator

Modular exponentiation calculates the remainder when an integer base is raised to a nonnegative integer exponent and divided by a positive modulus. The expression a^b mod m asks for the unique remainder from 0 through m - 1 that is congruent to a^b. A direct calculation can become impractical very quickly because powers grow to enormous sizes, even when the final remainder is small. This calculator avoids constructing that enormous intermediate integer. The efficient method is called binary exponentiation, repeated squaring, or square and multiply. Write the exponent in binary and process its bits. The base is first reduced modulo m. At each step, the current factor is squared modulo m. When the corresponding exponent bit is one, that factor is multiplied into the result, again reducing modulo m immediately. Because every intermediate value is reduced, it remains smaller than the square of the modulus. This algorithm needs only a number of steps proportional to the logarithm of the exponent. Computing a power with exponent one billion therefore requires only about thirty squaring stages rather than one billion repeated multiplications. The displayed operation count separates squarings from the selected multiplications associated with one bits in the exponent. An exponent of zero correctly returns 1 mod m. Modular arithmetic treats numbers with the same remainder as equivalent. For example, 17 and 5 are congruent modulo 12 because both leave remainder 5. A negative base is also supported: it is first normalized to a nonnegative residue. The exponent must be nonnegative in this calculator. Negative modular exponents require finding a modular multiplicative inverse, which exists only when the base and modulus are coprime. Modular powers are fundamental to number theory and modern cryptography. RSA encryption and signatures raise messages to large powers modulo a composite number. Diffie-Hellman key exchange and many discrete-logarithm systems use powers modulo a prime. The same operation also supports primality tests, pseudorandom generators, checksums, cyclic patterns, and programming contest problems. All three fields are processed as exact arbitrary-size integers rather than floating-point numbers. That means values beyond JavaScript's usual safe integer limit retain every digit. The modulus must be greater than one, and no commas or decimal points should be entered. For a useful manual check, reduce the base first and verify small exponents through repeated multiplication, taking the remainder after every step.