Understanding Modular Exponentiation
Modular exponentiation computes be mod m -- the remainder when b raised to the power e is divided by m. Direct computation is impractical for large numbers (like those used in cryptography), so the "repeated squaring" (binary exponentiation) algorithm is used instead.
The Algorithm
Binary Exponentiation
Convert exponent to binary. Square and multiply based on each bit.
O(log e) multiplications
Key Property
We can reduce mod m at each step, keeping numbers small.
(a x b) mod m = ((a mod m) x (b mod m)) mod m
RSA Encryption
RSA relies on modular exponentiation with very large primes.
c = m^e mod n
How Repeated Squaring Works
- Write the exponent e in binary: e = (b_k b_(k-1) ... b_1 b_0)_2.
- Start with result = 1.
- For each bit from left to right (most significant to least): square the result (mod m), then if the bit is 1, multiply by the base (mod m).
- This computes b^e mod m in O(log e) multiplications instead of O(e).
Example: 713 mod 11
13 in binary = 1101. Process: start with 1, then for each bit:
- Bit 1: 1^2 = 1, multiply by 7: 1 x 7 = 7 mod 11 = 7
- Bit 1: 7^2 = 49, 49 mod 11 = 5, multiply by 7: 5 x 7 = 35 mod 11 = 2
- Bit 0: 2^2 = 4, 4 mod 11 = 4 (no multiply, bit is 0)
- Bit 1: 4^2 = 16, 16 mod 11 = 5, multiply by 7: 5 x 7 = 35 mod 11 = 2
Result: 713 mod 11 = 2.
Applications
- RSA Cryptography: Encryption and decryption both use modular exponentiation.
- Diffie-Hellman: Key exchange protocol relies on discrete logarithms and modular exponentiation.
- Primality Testing: Miller-Rabin and Fermat tests use modular exponentiation.
- Digital Signatures: DSA and similar algorithms.
- Number Theory: Computing orders of elements, solving congruences.