Power Mod Calculator
Calculate modular exponentiation (a^b mod n) efficiently using fast algorithms
Modular Exponentiation Calculator
The base number to be raised to a power
The power to which the base is raised (must be non-negative)
The modulus value (must be positive)
Example Calculations
Example 1: Direct Method
Calculate: 5⁴ mod 3
Solution: 5⁴ = 625, so 625 mod 3 = 1
Verification: 625 = 208 × 3 + 1
Example 2: Using Fermat's Little Theorem
Calculate: 162⁶⁰ mod 61
Solution: Since 61 is prime and gcd(162, 61) = 1
By Fermat's Little Theorem: 162⁶⁰ ≡ 1 (mod 61)
Example 3: Large Numbers
Calculate: 123⁴⁵⁶ mod 789
Method: Use binary exponentiation algorithm
Result: 699 (calculated using fast algorithm)
Modular Exponentiation Formula
where 0 ≤ result < n
x: Base number
y: Exponent (≥ 0)
n: Modulus (> 0)
Binary Exponentiation
Efficiency
O(log n) time complexity
Method
Square and multiply technique
Application
Cryptography, number theory
Useful Theorems
Fermat's Little Theorem
If p is prime and gcd(a,p) = 1, then a^(p-1) ≡ 1 (mod p)
Euler's Theorem
If gcd(a,n) = 1, then a^φ(n) ≡ 1 (mod n)
Chinese Remainder
Helps solve systems of modular equations
Quick Tips
Use binary exponentiation for large numbers
Apply Fermat's theorem when modulus is prime
Always reduce intermediate results modulo n
Check if base and modulus are coprime
Understanding Modular Exponentiation
What is Modular Exponentiation?
Modular exponentiation is the operation of computing x^y mod n, where we find the remainder when x raised to the power y is divided by n. This operation is fundamental in number theory, cryptography, and computer science.
Why Use Fast Algorithms?
For large numbers, computing x^y directly would result in astronomically large numbers that are impractical to handle. Binary exponentiation reduces the time complexity from O(y) to O(log y), making it feasible to compute even for very large exponents.
Applications
- •RSA encryption and digital signatures
- •Primality testing algorithms
- •Discrete logarithm problems
- •Hash function implementations
Binary Exponentiation Algorithm
Step-by-step Process
- 1. Convert exponent to binary
- 2. Initialize result = 1, base = x mod n
- 3. For each bit from right to left:
- - If bit is 1: result = (result × base) mod n
- - Square the base: base = (base²) mod n
- 4. Return result
Mathematical Optimization
Fermat's Little Theorem
For prime modulus p and gcd(a,p) = 1: a^(p-1) ≡ 1 (mod p)
Euler's Theorem
For gcd(a,n) = 1: a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function
Small Example
5⁴ mod 3
5⁴ = 625
625 ÷ 3 = 208 remainder 1
Result: 1
Using Theorem
7¹⁰ mod 11
11 is prime, so by FLT:
7¹⁰ ≡ 1 (mod 11)
Result: 1
Binary Method
3⁵ mod 7
5 = 101₂
Process: 3¹ × 3⁴ = 3 × 4 = 5
Result: 5