Modular exponentiation calculator

Base b

Exponent e

Modulus n

 Compute b^e mod n

65^17 mod 3233 (RSA, encrypt)2790^2753 mod 3233 (RSA, decrypt)2^340 mod 3413^340 mod 341A huge exponent

Exact big-integer arithmetic in your browser. Nothing is sent anywhere.

This modular exponentiation calculator computes b^e mod n, the remainder you get when b is multiplied by itself e times and divided by n, and it shows the square-and-multiply steps that make huge exponents possible. The numbers can have up to 400 digits, and it runs in your browser.

Using it

Enter a base, an exponent and a modulus. The tool shows the exponent in binary and every squaring and multiplication of the fast method, then counts how much work it did against the naive approach. The first sample is a complete RSA round trip in miniature. 65¹⁷ mod 3,233 is 2,790, and 2,790²⁷⁵³ mod 3,233 is 65 again.

Why you can't just multiply

An RSA message is raised to a power of about 2,048 bits, an exponent with more than 600 digits. Multiplying a number by itself that many times would take more steps than there are atoms in the universe (the page works out 10⁶¹⁷ for a 2,048-bit exponent). Even writing down the result before taking the remainder is impossible. 65²⁷⁵³ already has 4,991 digits, and with a 2,048-bit exponent the result would have more digits than there are particles in the observable universe. Two observations make the method workable.

• Reduce as you go. The remainder of a product depends only on the remainders of the factors, so you can take the remainder after every multiplication and never hold a number larger than n².
• Square instead of repeating. b¹⁶ takes four squarings (b, b², b⁴, b⁸, b¹⁶), not fifteen multiplications.

Square and multiply

Write the exponent in binary and process the bits from the left. Start with 1. For each bit, square the running value, and if the bit is 1, also multiply by the base. For 65¹⁷ mod 3,233 the exponent is 17, which is 10001 in binary:

bit 1: square 1 → 1, multiply by 65 → 65
bit 0: square 65 → 4225 mod 3233 = 992
bit 0: square 992 → 1232
bit 0: square 1232 → 1547
bit 1: square 1547 → 789, multiply by 65 → 2790

That's five squarings and two multiplications instead of sixteen multiplications, and the saving grows fast. An exponent with k bits needs at most 2k operations, whatever its size. A 2,048-bit modulus with the usual public exponent 65,537 (a 17-bit number with only two 1-bits) needs about 17 squarings and one extra multiplication to encrypt. Decryption uses the full-size private exponent, so it takes roughly a hundred times as long, which is why RSA decryption is slower than encryption. On the machine that produced the example numbers, generating two 1,024-bit primes took the bulk of 1.3 seconds, and the decryption itself took about 26 milliseconds (scripts/examples/maths-tools-examples.mjs).

Where else it shows up

• The Fermat test and Miller–Rabin. Testing a prime means computing aⁿ⁻¹ mod n. Try 2³⁴⁰ mod 341. The answer is 1, even though 341 = 11 × 31 isn't prime, but 3³⁴⁰ mod 341 gives 56, which exposes it. The prime-or-not game and the checker are built on this operation.
• Diffie–Hellman and ElGamal. Each side computes g^a mod p with a huge secret a. Going forward is fast. Going backward, finding a from the result, is the discrete logarithm problem, which has no known fast solution (Diffie–Hellman, discrete log tool).
• RSA. Encrypt, decrypt and sign are each one modular exponentiation (RSA).

The speed comes with a security cost that implementers have to know about. The running time depends on the exponent's bits, so a naive version leaks the private exponent through timing and power use, and real libraries use constant-time variants. cipher.ink's own cryptography, AES-GCM, doesn't use modular exponentiation. This page is for learning, not for protecting a secret, so never paste a real private key into any website.

Common questions