How this calculator works
A power such as 2^10000 has thousands of digits, but its remainder after division by 1000 has only three. Modular exponentiation exploits that: after every multiplication the result is reduced modulo n, so the numbers never grow past n². Repeated squaring cuts the work to about log₂(y) multiplications, which is why an exponent of a quadrillion still finishes instantly.
Formula
x^y mod n is computed by setting r = 1, then for each bit of y from the highest to the lowest: r = r² mod n, and if the bit is 1 then r = r × x mod n. The final r is the answer.
Worked example
2^10 = 1024, and 1024 mod 1000 = 24. Using 3^100 mod 7: 3^6 ≡ 1 (mod 7) by Fermat's little theorem, and 100 = 6 × 16 + 4, so the result is 3^4 = 81 ≡ 4 (mod 7).
Advertisement
Frequently asked questions
What does 0^0 mean here?
This calculator uses the combinatorics convention 0^0 = 1, so the result is 1 mod n. In analysis the expression is often left undefined; the convention is stated so the answer is never a surprise.
Can the base be negative?
Yes. The base is first reduced into the range 0 to n - 1, so -2 mod 5 becomes 3. The reported x mod n output shows that reduced value.
Why is a modulus of 1 allowed?
Every integer leaves remainder 0 when divided by 1, so the answer is always 0. It is a valid but trivial case.
What is this used for?
Modular exponentiation is the core of public-key cryptography such as RSA and Diffie-Hellman, and of primality tests. It also checks last digits of huge powers.