Modular Exponentiation Calculator
Calculate a^b mod m using fast exponentiation. Essential for cryptography and number theory.
Input
Common examples:
3^13 mod 7
3
Binary Representation of Exponent
13 = (1101)â‚‚
4 bits
Euler's Totient
φ(7) = 6
If gcd(3, 7) = 1, then 3^6 ≡ 1 (mod 7)
Power Table
3^1 ≡ 33^2 ≡ 23^3 ≡ 63^4 ≡ 43^5 ≡ 53^6 ≡ 13^7 ≡ 33^8 ≡ 23^9 ≡ 63^10 ≡ 43^11 ≡ 53^12 ≡ 13^13 ≡ 3
Square-and-Multiply Steps
result = 1 Ă— 3 mod 7 = 3
base = 3² mod 7 = 2
base = 2² mod 7 = 4
result = 3 Ă— 4 mod 7 = 5
base = 4² mod 7 = 2
result = 5 Ă— 2 mod 7 = 3
Square-and-Multiply Algorithm
How It Works
Instead of multiplying b by itself e times, we use the binary representation of e. For each bit, we square the base. For each 1-bit, we also multiply into the result.
Complexity
Time: O(log e) multiplications instead of O(e). Critical for cryptography where e can have hundreds of digits.