numvana

Modular Exponentiation Calculator

Compute base^exponent mod modulus using fast square-and-multiply exponentiation — the algorithm behind RSA and other public-key cryptography.

4^13 mod 497
445

How it works

This computes base^exponent mod modulus using square-and-multiply (binary exponentiation), the standard algorithm for this problem rather than raising base to exponent first and reducing afterward — that would produce a number far too large to represent exactly once the exponent gets even moderately large.

The exponent is repeatedly halved: at each step the base is squared (and reduced mod modulus immediately, keeping every intermediate value small), and if the current bit of the exponent is 1, that squared value is folded into the running result. This takes only about log₂(exponent) multiplications instead of exponent − 1 of them, which is what makes modular exponentiation practical even for the huge exponents used in real cryptographic keys.

A negative base is first normalized into the range [0, modulus) before the algorithm runs, so the result always matches the standard non-negative convention for a modular remainder.

FAQ

Why does this matter for cryptography?

RSA encryption and decryption, Diffie-Hellman key exchange, and many other public-key algorithms are built entirely on modular exponentiation with very large numbers (hundreds of digits). Square-and-multiply is what makes computing those results feasible in a reasonable amount of time — without it, even a single RSA operation would be computationally infeasible.

Why is there a safe-integer limit on the inputs?

This calculator runs on BigInt internally, which keeps every intermediate multiplication exact no matter how large the numbers get — but the inputs and final result still have to round-trip through JavaScript's Number type for display, and Number can only represent integers exactly up to 2^53 − 1 (Number.MAX_SAFE_INTEGER). Real cryptographic keys use numbers far beyond that range and need a dedicated big-integer library, not a simple web calculator.

Related calculators