How does binary exponentiation work?

Binary exponentiation (also called exponentiation by squaring) converts the exponent to binary, then processes each bit from left to right. For each bit, it squares the current result (modular). If the bit is 1, it also multiplies by the base (modular). This reduces the number of multiplications from b-1 to at most 2*log2(b).

Modular Exponentiation Calculator

Calculate modular exponentiation a^b mod n efficiently using the binary exponentiation (fast power) algorithm. Enter the base, exponent, and modulus to get instant results with a step-by-step breakdown of the squaring-and-multiply method, binary decomposition visualization, and cryptographic context.

Embed Modular Exponentiation Calculator Widget

About Modular Exponentiation Calculator

The Modular Exponentiation Calculator computes \(a^b \bmod n\) — raising a base \(a\) to an exponent \(b\) and taking the remainder when divided by modulus \(n\). It uses the binary exponentiation algorithm (also called fast power or exponentiation by squaring), which reduces the operation from \(O(b)\) multiplications to just \(O(\log b)\). This is the same algorithm used in real-world cryptographic implementations like RSA, Diffie-Hellman, and ElGamal.

Applications of Modular Exponentiation

🔐

RSA Encryption

Encrypt and decrypt messages using modular exponentiation with large prime products

🤝

Diffie-Hellman

Key exchange protocol computing g^a mod p for secure shared secrets

✍

Digital Signatures

DSA, ECDSA, and EdDSA all rely on modular exponentiation

🧪

Primality Testing

Fermat and Miller-Rabin tests use a^(n-1) mod n to check primality

🏆

Competitive Programming

Modular arithmetic with fast power is essential for contest problems

🔗

Blockchain

Proof-of-work and cryptographic hashing rely on modular arithmetic

How the Binary Exponentiation Algorithm Works

The key insight is that we can decompose any exponent into a sum of powers of 2 using its binary representation. For example, \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\), so \(a^{13} = a^{8} \times a^{4} \times a^{1}\).

The algorithm processes the binary digits of the exponent from left to right:

Step 1: Convert the exponent \(b\) to binary.

Step 2: Initialize result = 1 (or = base if first bit is 1).

Step 3: For each subsequent bit: Square the result (mod n). If the bit is 1, also multiply by the base (mod n).

Step 4: After all bits are processed, the result is \(a^b \bmod n\).

Pseudocode

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // bit is 1
            result = (result × base) mod mod
        exp = exp >> 1        // shift right (divide by 2)
        base = (base × base) mod mod
    return result

Key Formulas

Property	Formula	Description
Modular Exponentiation	\(a^b \bmod n\)	Remainder of a^b divided by n
Fermat's Little Theorem	\(a^{p-1} \equiv 1 \pmod{p}\)	For prime p and gcd(a,p)=1
Euler's Theorem	\(a^{\phi(n)} \equiv 1 \pmod{n}\)	For gcd(a,n)=1, where φ is Euler's totient
Binary Method Complexity	\(O(\log b)\) multiplications	At most 2·log₂(b) modular multiplications
RSA Encryption	\(c = m^e \bmod n\)	Encrypt message m with public key (e, n)
RSA Decryption	\(m = c^d \bmod n\)	Decrypt ciphertext c with private key d

How to Use the Modular Exponentiation Calculator

Enter the base (a): This is the number you want to raise to a power. It can be positive or negative. For example, enter 7 for computing 7^256 mod 13.
Enter the exponent (b): This must be a non-negative integer. It represents the power. For cryptographic applications, this can be very large (the calculator supports up to 10^18).
Enter the modulus (n): This must be a positive integer. It is the number you divide by to get the remainder. In RSA, this is typically the product of two large primes.
Click Calculate: The calculator computes a^b mod n using binary exponentiation and shows the result instantly.
Watch the animation: Press Play to watch the binary exponentiation algorithm execute step by step. Each bit of the exponent is processed in sequence, showing whether the algorithm squares, or squares and multiplies.
Review the trace: The step-by-step table shows every intermediate computation, and the efficiency comparison shows how much faster binary exponentiation is versus naive repeated multiplication.

Why Binary Exponentiation is Fast

Consider computing \(2^{1000} \bmod 13\). The naive approach requires 999 multiplications. Binary exponentiation converts 1000 to binary (1111101000), which has 10 bits. It needs at most 9 squarings plus a few multiplies for each '1' bit — roughly 15 operations total. That is about 98.5% fewer operations. For cryptographic-scale exponents with hundreds of digits, the difference is astronomical: binary method takes thousands of operations where naive would require more operations than atoms in the universe.

FAQ

What is modular exponentiation?

Modular exponentiation computes (a^b) mod n — it raises a base to an exponent, then takes the remainder when divided by a modulus. It is the core operation in public-key cryptography (RSA, Diffie-Hellman, ElGamal) and is used extensively in number theory, competitive programming, and computer science. The binary exponentiation method computes this efficiently in O(log b) multiplications.

How does binary exponentiation (exponentiation by squaring) work?

Binary exponentiation converts the exponent to its binary representation, then processes each bit from left to right (or right to left). For each bit, it squares the current result modulo n. If the bit is 1, it additionally multiplies the result by the base modulo n. This reduces the number of multiplications from b−1 (naive method) to at most 2×log₂(b), making it feasible to compute with enormous exponents.

Why is modular exponentiation important in cryptography?

RSA encryption computes c = m^e mod n for encryption and m = c^d mod n for decryption, where n is a product of two large primes and the exponents can be hundreds of digits long. Without fast modular exponentiation, these operations would be computationally impossible. The security relies on the fact that the reverse operation (computing the discrete logarithm) is believed to be computationally infeasible.

Can the base be negative?

Yes, negative bases are fully supported. The calculator first reduces the base modulo n (using Python's modular arithmetic, which always returns a non-negative result for positive n). For example, (−3)^2 mod 7 = 9 mod 7 = 2. Negative results never occur because the modular reduction always produces a value in the range [0, n−1].

What happens when the modulus is 1?

Any integer modulo 1 equals 0. This is because dividing any integer by 1 gives the integer itself with a remainder of 0. So a^b mod 1 = 0 for all values of a and b. The calculator handles this as a special case.

Reference this content, page, or tool as:

"Modular Exponentiation Calculator" at https://MiniWebtool.com/modular-exponentiation-calculator/ from MiniWebtool, https://MiniWebtool.com/

by miniwebtool team. Updated: 2026-04-16

You can also try our AI Math Solver GPT to solve your math problems through natural language question and answer.

Related MiniWebtools:

Chinese Remainder Theorem Calculator

Euler's Totient Function Calculator

Exponents Calculator

Modular Multiplicative Inverse Calculator

Prime Factorization Calculator

Primitive Root CalculatorFeatured

Modular Exponentiation Calculator

About Modular Exponentiation Calculator

Applications of Modular Exponentiation

How the Binary Exponentiation Algorithm Works

Pseudocode

Key Formulas

How to Use the Modular Exponentiation Calculator

Why Binary Exponentiation is Fast

FAQ

Related MiniWebtools:

Advanced Math Operations:

Top & Updated: