Calculer modular exponentiation efficiently
Calculer base^exponent mod modulus efficiently using the square-and-multiply algorithm. Essential for cryptography.
- 1
Modular exponentiation computes base^exp mod m without calculating the enormous base^exp first. The square-and-multiply algorithm processes each bit of the exponent: square the result for each bit, multiply by base if the bit is 1, take mod at each step. This is O(log exp) instead of O(exp) — critical for crypto where exp has 2048+ bits.
- 2 Exponentiation modulaire →
Calculer base^exp mod m directly. Enter base, exponent, and modulus. The tool uses the efficient algorithm — even with a 2048-bit exponent, it completes instantly. This is the foundation of RSA, Diffie-Hellman, and other cryptographic operations.
- 3 Calculatrice de précision →
Verify the result with small numbers. For example, 3^5 mod 7 = 243 mod 7 = 5. The modular exponentiation tool should give the same result. This sanity check verifies the algorithm is working correctly.
Questions fréquentes
- Why is naive exponentiation impractical for crypto?
- RSA uses exponents with 2048+ bits. 2^2048 is a number with 617 digits — computing it directly would require more memory than exists on Earth. Modular exponentiation keeps intermediate results small (always < m) by taking mod at each step, making it feasible.
- What is the square-and-multiply algorithm?
- Process the exponent bit by bit. Start with result = 1. For each bit (MSB to LSB): result = result^2 mod m (square); if the bit is 1, result = result * base mod m (multiply). This processes each bit with at most 2 multiplications — O(log exp) total.