Last verified · v1.0

Calculator · math

Power Modulo Calculator

Compute base^exponent mod modulus instantly. Uses fast modular exponentiation for large values — essential for cryptography, number theory, and RSA calculations.

FreeInstantNo signupOpen source

Inputs

Base

Exponent

Modulus

Result (base^exponent mod modulus)

—

Get a plain-English breakdown of your result with practical next steps.

Result (base^exponent mod modulus)—

The formula

How the
result is
computed.

What Is Modular Exponentiation?

Modular exponentiation computes the remainder when a base number raised to an exponent is divided by a modulus. The formal notation is a^b mod n, where a is the base, b is the exponent, and n is the modulus. This operation appears throughout number theory, computer science, and modern cryptography.

The Formula

The power modulo formula is:

result = base^exponent mod modulus

For a concrete example, compute 3⁴ mod 7: first calculate 3⁴ = 81, then divide 81 by 7 to obtain a remainder of 4. Therefore, 3⁴ mod 7 = 4. The result always falls in the range [0, n-1], regardless of how large the base or exponent becomes.

Understanding the Variables

Base (a): The number being raised to a power. Accepts any integer, including values larger than the modulus; the calculator reduces it automatically on the first step.
Exponent (b): A non-negative integer specifying how many times the base multiplies itself. An exponent of 0 always yields 1, since a⁰ = 1 for any non-zero base.
Modulus (n): A positive integer that defines the cycle length of the arithmetic system. Every result is an element of the set {0, 1, 2, ..., n-1}.

Fast Modular Exponentiation Algorithm

Computing a^b directly for large exponents is computationally infeasible. For instance, 7¹⁰⁰⁰ produces a number with over 845 digits — far beyond what any machine can store or multiply conventionally. The fast modular exponentiation algorithm, also called repeated squaring or binary exponentiation, solves this by decomposing the exponent into powers of 2.

The algorithm proceeds as follows:

Express the exponent in binary form.
Initialize the result to 1.
Scan each bit from most significant to least significant: square the current result and reduce modulo n. If the current bit is 1, also multiply by the base and reduce modulo n.

According to Khan Academy's article on fast modular exponentiation, this technique reduces computations that would otherwise require billions of multiplications to just a few dozen operations, making it the indispensable engine behind real-world cryptographic systems. For example, computing 5¹³ mod 23 requires expressing 13 in binary as 1101, which yields at most 2 × log₂(13) ≈ 8 multiplications rather than 12 sequential ones.

Why Modular Arithmetic Matters

Modular arithmetic establishes equivalence classes called congruences: two integers a and b are congruent modulo n (written a ≡ b mod n) if they share the same remainder when divided by n. As Gordon College's introduction to number theory explains, this structure underlies clock arithmetic, cyclic groups, and the security guarantees of modern encryption.

Key applications of modular exponentiation include:

RSA Encryption: Encryption computes c = m^e mod n; decryption computes m = c^d mod n, where e and d are paired public and private keys.
Diffie-Hellman Key Exchange: Both parties independently compute g^x mod p for a shared prime p and generator g, deriving the same secret without ever transmitting it.
Miller-Rabin Primality Testing: This probabilistic test checks primality by verifying specific modular exponentiation conditions on candidate numbers, powering most real-world prime generation routines.
Hash Functions and Checksums: Modular reduction produces fixed-size outputs from variable-length inputs, forming the basis of many integrity-verification algorithms.

Worked Examples

Example 1: Basic Calculation

Compute 2¹⁰ mod 1000: 2¹⁰ = 1024, and 1024 mod 1000 = 24.

Example 2: Large Exponent via Repeated Squaring

Compute 7⁸ mod 13 step by step: 7¹ mod 13 = 7; 7² mod 13 = 49 mod 13 = 10; 7⁴ mod 13 = 100 mod 13 = 9; 7⁸ mod 13 = 81 mod 13 = 3. Each step reduces the intermediate value, keeping arithmetic manageable.

Example 3: Simplified RSA

With modulus n = 33 and public exponent e = 7, encrypting message m = 2 gives: c = 2⁷ mod 33 = 128 mod 33 = 29. The recipient reverses this with the private key using the same modular exponentiation operation.

Reference

Frequently asked questions

What is a power modulo calculator used for?

A power modulo calculator computes base^exponent mod modulus — the remainder after dividing a large power by a given number. It is indispensable in cryptography (RSA, Diffie-Hellman), number theory coursework, primality testing (Miller-Rabin), and digital signature schemes. Without fast modular exponentiation, encrypting a single message with a 2048-bit RSA key would require handling numbers with hundreds of millions of digits, which is computationally impossible by brute force.

How does fast modular exponentiation reduce computation time?

Fast modular exponentiation uses repeated squaring to compute base^exponent mod modulus in O(log exponent) multiplications instead of O(exponent) multiplications. For a 256-bit exponent, this reduces approximately 10^77 multiplications down to just 512 operations. The algorithm expresses the exponent in binary and squares the running result at each bit position, multiplying by the base only when that bit is 1, and reducing modulo n after every step to prevent intermediate values from growing large.

What real-world applications rely on modular exponentiation?

Modular exponentiation is the mathematical core of RSA public-key encryption, Diffie-Hellman and elliptic-curve key exchange protocols, digital signature algorithms (DSA, ECDSA), and the Miller-Rabin primality test. Every time a browser opens an HTTPS connection, it performs modular exponentiation to negotiate a secure session key. The operation also appears in pseudo-random number generators, hash-based message authentication codes (HMAC), and zero-knowledge proof systems used in modern blockchain protocols.

Can the base be larger than the modulus in a power modulo calculation?

Yes, the base can exceed the modulus without affecting correctness. A fundamental property of modular arithmetic states that (a mod n)^b mod n equals a^b mod n. So 15^3 mod 7 reduces as (15 mod 7)^3 mod 7 = 1^3 mod 7 = 1. The calculator applies this reduction automatically on the first step, bringing the base into the range [0, n-1] before continuing, which also speeds up subsequent squaring operations.

What happens when the exponent is 0 in a power modulo calculation?

Any non-zero base raised to the exponent 0 equals 1 by the fundamental definition of exponentiation. Therefore, base^0 mod n equals 1 mod n, which is 1 for any modulus n greater than 1. The special case 0^0 is mathematically undefined, though many computing environments assign it the value 1 by convention. This calculator accepts 0 as a valid exponent input, always returning 1 in that scenario for any non-zero base.

How do I verify a power modulo result manually for small values?

For small inputs, compute the full power first and then take the remainder by dividing and keeping only what is left over. For 4^3 mod 5: 4^3 = 64, and 64 divided by 5 gives 12 with remainder 4, so the result is 4. For slightly larger inputs, apply repeated squaring step by step: 4^2 mod 5 = 16 mod 5 = 1, then 4^3 mod 5 = (1 × 4) mod 5 = 4. Both approaches confirm the same answer and build intuition for the algorithm.