Modular Exponentiation
Calculate a^b mod m efficiently using binary exponentiation
Modular exponentiation computes a^b mod m efficiently using the binary exponentiation (also called "exponentiation by squaring") algorithm. Instead of multiplying a by itself b times (which would be O(b) operations), this method reduces the complexity to O(log b).
- Convert the exponent b to its binary representation
- Initialize result = 1 and base = a mod m
- For each bit of b (from least to most significant):
- If the current bit is 1, multiply result by base (mod m)
- Square the base (mod m) for the next iteration
- The final result is a^b mod m
Applications: RSA encryption, Diffie-Hellman key exchange, primality testing (Miller-Rabin), digital signatures, and many other cryptographic protocols rely on efficient modular exponentiation.
Example: To compute 7^256 mod 13, instead of 256 multiplications, we only need about 8 iterations (log2(256) = 8), making it practical even for very large exponents.
Verifying Results with Fermat's Little Theorem: For a prime p and any integer a not divisible by p, Fermat's Little Theorem states that a^(p-1) ≡ 1 (mod p). This provides a quick way to verify results: you can reduce the exponent modulo (p-1) before computing.
Verification example: For 3^13 mod 7, since 7 is prime and gcd(3,7)=1, we know 3^6 ≡ 1 (mod 7). Since 13 = 2×6 + 1, we have 3^13 = (3^6)^2 × 3 ≡ 1^2 × 3 ≡ 3 (mod 7). This confirms our calculator's result.
Why is modular exponentiation important in cryptography?
Modular exponentiation is the core operation in RSA encryption, Diffie-Hellman key exchange, and digital signatures. Its security relies on the fact that computing a^b mod m is easy, but reversing it (discrete logarithm problem) is computationally infeasible for large numbers, forming the basis of public-key cryptography.
What is binary exponentiation and why is it efficient?
Binary exponentiation (also called exponentiation by squaring) reduces the number of multiplications from b to log2(b). Instead of multiplying a by itself b times, it converts b to binary and uses the property that a^b = a^(2^k1) * a^(2^k2) * ... for set bits. This makes computing 7^256 mod 13 require only ~8 operations instead of 256.
How does Fermat's Little Theorem help verify results?
Fermat's Little Theorem states that for prime p and a not divisible by p: a^(p-1) = 1 (mod p). This means you can reduce exponents modulo (p-1) before computing. For example, 3^100 mod 7 equals 3^(100 mod 6) mod 7 = 3^4 mod 7 = 81 mod 7 = 4.
Can modular exponentiation handle negative bases or exponents?
Negative bases work by first reducing mod m: (-3)^5 mod 7 = (4)^5 mod 7. Negative exponents require finding modular inverses: a^(-b) mod m = (a^(-1))^b mod m, which only exists when gcd(a,m)=1. This calculator handles non-negative exponents; for negative ones, first compute the modular inverse.