Power Mod Calculator
Free Power mod Calculator for arithmetic. Enter values to get step-by-step solutions with formulas and graphs. See charts, tables, and visual results.
Reviewed for accuracy by Manoj Kumar, Mathematics Educator
Power Mod Calculator
Calculator
Adjust values & calculateEnter your values below. Every result is computed in your browser — no data is sent to any server.
Formula: b^e mod m (computed via repeated squaring)
Worked example — 7^13 mod 11 = 2
Formula
b^e mod m (computed via repeated squaring)
Modular exponentiation computes base^exponent mod modulus efficiently by converting the exponent to binary and performing at most 2*log2(exponent) modular multiplications. At each step, the intermediate result is reduced modulo m, keeping all numbers manageable.
Worked Examples
Example 1: RSA-Style Computation
Problem:Compute 7^13 mod 11 using the repeated squaring method.
Solution:13 in binary = 1101 Step 1: bit 0 is 1, result = 1 * 7 = 7 mod 11 = 7, square: 7^2 = 49 mod 11 = 5 Step 2: bit 1 is 0, skip multiply, square: 5^2 = 25 mod 11 = 3 Step 3: bit 2 is 1, result = 7 * 3 = 21 mod 11 = 10, square: 3^2 = 9 mod 11 = 9 Step 4: bit 3 is 1, result = 10 * 9 = 90 mod 11 = 2 Verification: 7^13 = 96889010407 mod 11 = 2
Result:7^13 mod 11 = 2
Example 2: Large Exponent with Euler Reduction
Problem:Compute 3^1000 mod 7 using Euler theorem.
Solution:phi(7) = 6 (since 7 is prime) By Euler theorem: 3^6 mod 7 = 1 Reduce exponent: 1000 mod 6 = 4 So 3^1000 mod 7 = 3^4 mod 7 3^4 = 81 81 mod 7 = 81 - 11*7 = 81 - 77 = 4
Result:3^1000 mod 7 = 4 (reduced exponent from 1000 to 4)
Frequently Asked Questions
What is modular exponentiation and why is it important?
Modular exponentiation computes the remainder when a base number raised to an exponent is divided by a modulus, expressed as b^e mod m. This operation is fundamental to modern cryptography, particularly RSA encryption, Diffie-Hellman key exchange, and digital signatures. Without efficient modular exponentiation, secure internet communication would be practically impossible. The direct approach of first computing b^e and then taking the remainder is infeasible for cryptographic-size numbers (hundreds of digits) because the intermediate result would have billions of digits. Instead, algorithms like repeated squaring keep intermediate values small by reducing modulo m at each step. This makes it possible to compute results like 2^1000000 mod 997 almost instantly, even though 2^1000000 is a number with over 300,000 digits.
How does the repeated squaring algorithm work?
The repeated squaring algorithm, also called binary exponentiation or fast exponentiation, converts the exponent to binary and processes each bit. Starting from the result 1, for each bit of the exponent from least significant to most significant, if the bit is 1, multiply the current result by the current power of the base (all mod m). Then square the current power for the next iteration. For example, to compute 3^13 mod 7, note that 13 in binary is 1101. Starting with result=1 and power=3: bit 1 is 1 so result=1*3=3, square power to 9 mod 7=2; bit 0 is 0 so skip, square power to 4; bit 1 is 1 so result=3*4=12 mod 7=5, square power to 16 mod 7=2; bit 1 is 1 so result=5*2=10 mod 7=3. The answer is 3. This reduces an O(e) multiplication problem to O(log e) multiplications.
What is Euler totient function and how does it relate to modular exponentiation?
Euler totient function, denoted phi(n), counts the number of integers from 1 to n that are coprime to n (share no common factors other than 1). For a prime p, phi(p) = p-1. For a product of two primes p*q, phi(p*q) = (p-1)(q-1), which is the formula used in RSA cryptography. Euler theorem states that if a and n are coprime, then a^phi(n) is congruent to 1 modulo n. This means a^e mod n = a^(e mod phi(n)) mod n, allowing us to reduce very large exponents before computing. For example, computing 3^1000000 mod 7: since phi(7) = 6, we reduce the exponent to 1000000 mod 6 = 4, so 3^1000000 mod 7 = 3^4 mod 7 = 81 mod 7 = 4. This property is essential for the mathematical foundation of RSA decryption.
How is modular exponentiation used in RSA encryption?
RSA encryption relies directly on modular exponentiation for both encryption and decryption. The public key consists of a modulus n (product of two large primes p and q) and an encryption exponent e. To encrypt a message M, compute C = M^e mod n. To decrypt, the recipient uses their private key exponent d (where e*d is congruent to 1 mod phi(n)) to compute M = C^d mod n. The security of RSA depends on the difficulty of factoring n back into p and q, which would reveal phi(n) and allow computing the private key d. In practice, RSA uses 2048-bit or larger keys, meaning the numbers involved have over 600 digits. Efficient modular exponentiation algorithms make these computations feasible in milliseconds, while factoring the modulus remains computationally infeasible.
What is the multiplicative order and how do you find it?
The multiplicative order of a modulo m is the smallest positive integer k such that a^k is congruent to 1 modulo m, provided a and m are coprime. It represents the period of the cyclic pattern formed by successive powers of a modulo m. By Lagrange theorem, the order always divides Euler totient phi(m). To find the order, you can check each divisor of phi(m) in ascending order until you find the smallest one where a^k mod m equals 1. For example, the order of 2 mod 7 is 3 because 2^1=2, 2^2=4, 2^3=8 mod 7=1. Knowledge of the order is useful in number theory, cryptanalysis, and generating pseudorandom numbers. In discrete logarithm problems, the order determines the size of the cyclic group in which the computation takes place.
What happens when the base and modulus are not coprime?
When the base b and modulus m share common factors (are not coprime), Euler theorem does not directly apply, and the behavior of b^e mod m becomes more nuanced. The sequence of powers b^0, b^1, b^2, ... mod m is still eventually periodic, but it may not start cycling from the beginning. Instead, there is a pre-period (also called the tail) before the cycle begins. For example, with b=6 and m=9, the powers modulo 9 are: 1, 6, 0, 0, 0, ... which reaches 0 and stays there. The generalized Euler theorem or the Carmichael function lambda(m) can handle these cases. In cryptographic applications, the base and modulus are typically chosen to be coprime, so this issue rarely arises in practice. However, understanding non-coprime cases is important for general number theory and certain computational algorithms.
How does modular exponentiation differ from regular exponentiation?
Regular exponentiation computes the full value of b^e, which grows exponentially and quickly becomes astronomically large. For example, 2^100 is already a 31-digit number, and 2^1000 has 302 digits. Modular exponentiation keeps all intermediate results bounded by the modulus m, making the computation tractable even for enormous exponents. The key insight is that (a * b) mod m = ((a mod m) * (b mod m)) mod m, meaning you can reduce modulo m at every multiplication step without affecting the final result. This property allows computing b^e mod m in O(log e) multiplications of numbers no larger than m^2, regardless of how large e is. While regular exponentiation produces a number with e * log(b) digits, modular exponentiation always produces a result between 0 and m-1, making it computationally practical for cryptographic applications.
What are some applications of modular exponentiation beyond cryptography?
Beyond cryptography, modular exponentiation appears in numerous computational contexts. In primality testing, algorithms like Miller-Rabin and Fermat tests compute a^(n-1) mod n to probabilistically determine if n is prime. Hash functions and pseudorandom number generators use modular exponentiation to produce well-distributed outputs. In competitive programming, problems frequently require computing large powers modulo a prime, especially when dealing with combinatorics and counting problems. Modular exponentiation is used in computing discrete logarithms, which appear in certain scheduling algorithms and error-correcting codes. In number theory research, it helps explore properties of cyclic groups, quadratic residues, and primitive roots. Even in everyday programming, modular exponentiation is useful when computing Fibonacci numbers modulo m, evaluating polynomial hashes, or implementing certain game theory algorithms.
What is the relationship between modular exponentiation and discrete logarithms?
Modular exponentiation and discrete logarithms are inverse operations: if modular exponentiation computes y = b^x mod m given b, x, and m, then the discrete logarithm finds x given b, y, and m. While modular exponentiation is computationally easy (polynomial time), finding the discrete logarithm is believed to be computationally hard for well-chosen parameters. This asymmetry is the foundation of several cryptographic systems including Diffie-Hellman key exchange and ElGamal encryption. The best-known algorithms for computing discrete logarithms in general groups, such as baby-step giant-step and Pollard rho, have sub-exponential or square-root complexity. For specific groups like those defined over elliptic curves, the discrete logarithm problem is even harder, which is why elliptic curve cryptography can use smaller key sizes than RSA while maintaining equivalent security.
How can you verify modular exponentiation results manually?
For small numbers, you can verify modular exponentiation results using several techniques. The most straightforward method is computing the full power and then taking the remainder, which works for small exponents. For larger exponents, use the repeated squaring method by hand: write the exponent in binary, then track the running result and squared base at each step. You can also use intermediate reduction, computing step by step: 3^5 mod 7 = 3 * 3^4 mod 7 = 3 * (3^2)^2 mod 7 = 3 * (9 mod 7)^2 mod 7 = 3 * 2^2 mod 7 = 3 * 4 mod 7 = 12 mod 7 = 5. Fermat little theorem provides a shortcut for prime moduli: if p is prime and gcd(a,p)=1, then a^(p-1) mod p = 1, so you can reduce the exponent modulo (p-1). Cross-checking with multiple methods increases confidence in the result.
References
Reviewed for accuracy by Manoj Kumar, Mathematics Educator · Editorial policy
Related Calculators
🧮Power Set Calculator
Calculate power set with inputs, formulas, and instant results.
🧮Power of a Power Calculator
Calculate power of apower with inputs, formulas, and instant results.
🧮E Calculator Eeraised to Power of X
Calculate ecalculator eeraised to power of x with inputs, formulas, and instant results.
🧮Matrix Power Calculator
Calculate matrix power with inputs, formulas, and instant results.
🧮Power Reducing Calculator
Calculate power reducing with inputs, formulas, and instant results.
🧮Annulus Area Calculator
Calculate annulus area with inputs, formulas, and instant results.
🧮Area Calculator
Calculate area with inputs, formulas, and instant results.
🧮Area of a Rectangle Calculator
Calculate the area, perimeter, and diagonal of a rectangle. Find missing sides from known area. Convert between metric and imperial area units.