Power Modulo
Compute modular exponentiation a^b mod n for any integers a, b, n using fast exponentiation. Free online number theory calculator for students and cryptography enthusiasts.
About This Calculator
About the Power Modulo Calculator
The Power Modulo Calculator computes modular exponentiation -- the result of raising a base number a to an exponent b and then taking the remainder modulo n. This operation is written as a^b mod n and is widely used in number theory, cryptography, and computer science. Whether you are a student studying modular arithmetic or a developer implementing cryptographic algorithms, this tool provides fast and accurate results.
How It Works
This calculator uses the exponentiation by squaring (fast modular exponentiation) algorithm. Instead of computing the enormous intermediate value a^b directly -- which can overflow standard number types even for modest inputs like 7^100 -- the algorithm processes each bit of the exponent. At every step, the base is squared and reduced modulo n, keeping all intermediate values within a manageable range. When the current bit of the exponent is 1, the accumulated result is multiplied by the current base and reduced again. This technique completes in O(log b) steps, making it efficient even for very large exponents.
Applications
Modular exponentiation is the backbone of public-key cryptography. The RSA algorithm encrypts and decrypts messages using modular exponentiation with large primes. The Diffie-Hellman key exchange protocol allows two parties to establish a shared secret over an insecure channel using modular exponentiation. Digital signatures, SSL/TLS certificates, and cryptocurrency transactions all depend on this fundamental operation. Outside of cryptography, modular exponentiation is used in primality tests (Miller-Rabin), hash-based message authentication codes (HMAC), and pseudorandom number generation.
Example
Compute 3^5 mod 7: Using the calculator, enter base = 3, exponent = 5, and modulus = 7. The result is 5, because 3^5 = 243, and 243 ÷ 7 = 34 remainder 5. You can verify: 7 x 34 = 238, and 243 - 238 = 5.
Compute 2^10 mod 1000: Enter base = 2, exponent = 10, modulus = 1000. The result is 24, because 2^10 = 1024, and 1024 mod 1000 = 24.
Frequently Asked Questions
What is modular exponentiation?
Modular exponentiation is the calculation of a^b mod n, where a is the base, b is the exponent, and n is the modulus. It computes the remainder when a raised to the power b is divided by n. For example, 3^5 mod 7 = 243 mod 7 = 5.
Why use fast modular exponentiation?
Directly computing a^b can produce astronomically large numbers that overflow regular integer types. Fast modular exponentiation (also called exponentiation by squaring) uses the binary representation of the exponent to compute the result in O(log b) steps, keeping intermediate values within the modulus range and avoiding overflow entirely.
How does exponentiation by squaring work?
The algorithm repeatedly squares the base and reduces it modulo n, while processing each bit of the exponent. If the current bit of the exponent is 1, the accumulated result is multiplied by the current base value and reduced modulo n. This approach computes the result in logarithmic time instead of linear time.
What are real-world applications of modular exponentiation?
Modular exponentiation is fundamental to modern cryptography. RSA encryption, Diffie-Hellman key exchange, and the Digital Signature Algorithm (DSA) all rely on fast modular exponentiation. It is also used in primality testing, hash functions, and checksum algorithms that power secure communications and data integrity worldwide.
What happens if the modulus is 0 or negative?
This calculator requires a positive modulus n. If you enter 0 or a negative value for the modulus, the calculator will not produce a result. The modulus n must be greater than 0 for modular arithmetic to be well-defined.
How do you verify the result of modular exponentiation?
You can verify the result by checking that the computed remainder r satisfies 0 <= r < n and that (a^b - r) is divisible by n. For small numbers, you can compute a^b directly and perform the division. For large numbers, you can use Fermat's little theorem a^(p-1) ≡ 1 (mod p) when n is prime and a is not divisible by n.
Is this tool free to use?
Yes, all calculators on Calculy are completely free to use with no registration or login required.