Power Mod
Compute a^b mod m using fast square-and-multiply. Essential for cryptography.
Did our AI summary help? Let us know.
Why: Understanding power mod helps you make better, data-driven decisions.
How: Enter Base (a), Exponent (b), Modulus (m) to calculate results.
Run the calculator when you are ready.
Enter Values
Binary Steps (Current Value)
Result mod 10
๐ Step-by-Step Breakdown
For educational and informational purposes only. Verify with a qualified professional.
๐ Key Takeaways
- โข a^b mod m = remainder when a^b is divided by m
- โข Square-and-multiply: O(log b) steps vs naive O(b)
- โข Essential for RSA, Diffie-Hellman, ElGamal
- โข Euler: a^ฯ(m) โก 1 (mod m) when gcd(a,m)=1
- โข Fermat: a^(p-1) โก 1 (mod p) for prime p, a not divisible by p
๐ก Did You Know?
๐ How It Works
Modular exponentiation computes a^b mod m without computing the full a^b (which would overflow). The square-and-multiply algorithm uses the binary expansion of b: for each bit from MSB to LSB, square the current result; if the bit is 1, multiply by a. Each step is done mod m, so numbers stay small. Complexity: O(log b) multiplications.
๐ Worked Example: 3^7 mod 10
7 in binary: 111
Start: result = 1
Bit 1: square 1โ1, multiply 1ร3โ3
Bit 1: square 3โ9, multiply 9ร3โ27โก7
Bit 1: square 7โ49โก9, multiply 9ร3โ27โก7
Result: 3^7 mod 10 = 7
๐ Real-World Applications
๐ RSA Encryption
Encryption/decryption use modular exponentiation.
๐ Diffie-Hellman
Key exchange: g^a mod p, g^b mod p.
๐ Digital Signatures
DSA, ECDSA rely on modPow.
๐ฒ PRNGs
Linear congruential and Blum Blum Shub.
๐ Hash Functions
Some constructions use modular exponentiation.
๐ Number Theory
Primality tests, discrete log.
โ ๏ธ Common Mistakes to Avoid
- Computing a^b first: Would overflow; always reduce mod m at each step.
- Negative exponent: a^(-b) mod m requires modular inverse; we assume b โฅ 0.
- Modulus 0: Division by zero is undefined.
- Wrong bit order: Square-and-multiply processes MSB first.
๐ฏ Expert Tips
๐ก Reduce Base First
Replace a with a mod m before starting to keep numbers small.
๐ก Fermat Shortcut
When m is prime: a^b mod m = a^(b mod (m-1)) mod m.
๐ก Zero Exponent
a^0 mod m = 1 for any a (when m > 1).
๐ก Verify
Check: (a^b) mod m should match. Use small test cases.
๐ Reference Table
| Expression | Result |
|---|---|
| 3^7 mod 10 | 7 |
| 2^10 mod 7 | 2 |
| 5^0 mod 13 | 1 |
| 2^8 mod 5 | 1 |
๐ Quick Reference
๐ Practice Problems
โ FAQ
What is modular exponentiation?
Computing a^b mod m โ the remainder when a^b is divided by m. Essential for cryptography.
Why square-and-multiply?
O(log b) steps vs naive O(b). For 2048-bit exponents, naive is impossible.
Can the exponent be negative?
a^(-b) mod m = (a^(-1))^b mod m requires modular inverse. This calculator uses b โฅ 0.
What if base is negative?
We reduce a mod m first, so we work with 0 โค a < m.
How does RSA use this?
Encryption: c = m^e mod n. Decryption: m = c^d mod n = m^(ed) mod n.
What is Fermat's little theorem?
For prime p: a^(p-1) โก 1 (mod p) when gcd(a,p)=1. So a^(-1) โก a^(p-2) mod p.
How do I verify?
For small b, compute a^b directly and take mod m. Should match.
๐ Summary
Modular exponentiation computes a^b mod m efficiently using the square-and-multiply algorithm. It is the backbone of RSA, Diffie-Hellman, and many cryptographic protocols. Always reduce mod m at each step to avoid overflow.
โ Verification Tip
For small exponents, verify manually: compute a^b, then take remainder mod m. For larger cases, check that the binary steps follow the algorithm correctly.
๐ Next Steps
Explore the Modulo Calculator for basic a mod b, the Inverse Modulo Calculator for a^(-1) mod m, or the Extended Euclidean Algorithm for Bรฉzout coefficients.
โ ๏ธ Disclaimer: For very large numbers, JavaScript precision may limit accuracy. Use established crypto libraries for production.
Related Calculators
Inverse Modulo Calculator
Find the modular multiplicative inverse a^(-1) mod m using the Extended Euclidean Algorithm. Requires gcd(a,m)=1. Step-by-step solutions for cryptography...
MathematicsExtended Euclidean Algorithm Calculator
Find gcd(a,b) and Bรฉzout coefficients x, y such that ax + by = gcd(a,b). Step-by-step division table. Modular inverse, linear Diophantine equations.
MathematicsChinese Remainder Theorem Calculator
Solve systems of congruence equations x โก a_i (mod m_i) using the Chinese Remainder Theorem. Step-by-step solution with multiple moduli, modular inverse, and...
MathematicsMultiplicative Inverse Modulo Calculator
Find the multiplicative inverse of a modulo m: aรx โก 1 (mod m). Uses the Extended Euclidean Algorithm with step-by-step trace. Applications in cryptography (RSA, Diffie-Hellman), linear congruences, and Chinese Remainder Theorem. Verify with Fermat's Little Theorem for prime moduli.
MathematicsAbsolute Change Calculator
Calculate absolute and relative change between two values. Get direction (increase/decrease), percentage impact, and step-by-step solutions. Simple mode for...
MathematicsAbsolute Value Calculator
Calculate the absolute value |x| of any number. Simple mode for basic |x|; advanced mode for |ax+b| expressions. Get distance from zero, step-by-step...
Mathematics