Modular Exponentiation Calculator

Calculate (baseexponent) mod modulus efficiently using fast exponentiation algorithms. Essential for cryptography and number theory.

Formula: Modular exponentiation computes (be) mod m efficiently, where b = base, e = exponent, m = modulus

This is fundamental to RSA encryption, Diffie-Hellman key exchange, and primality testing.

The number being raised to a power
The power to which the base is raised
The modulus for the calculation (must be > 0)
Common examples:
7¹³ mod 11
2¹⁰ mod 1000
3²⁰⁰ mod 50
5²³ mod 13
123⁴⁵⁶ mod 789
65537⁶⁵⁵³⁷ mod 10⁹+7
Calculating...

Understanding Modular Exponentiation

Modular exponentiation is the computation of be mod m, where b is the base, e is the exponent, and m is the modulus. It is a fundamental operation in number theory and cryptography.

Why modular exponentiation is important:

  • RSA Encryption: Encryption and decryption in RSA involve modular exponentiation with large numbers (typically 2048+ bits)
  • Diffie-Hellman Key Exchange: Secure key exchange protocol based on modular exponentiation
  • Digital Signatures: Many digital signature algorithms use modular exponentiation
  • Primality Testing: Miller-Rabin primality test uses modular exponentiation
  • Discrete Logarithms: Foundation of many cryptographic protocols

Fast Exponentiation Algorithms

1
Binary Exponentiation (Exponentiation by Squaring)

This algorithm reduces the number of multiplications from O(n) to O(log n) by using the binary representation of the exponent.

To compute be:
If e is even: be = (b2)e/2
If e is odd: be = b × (b2)(e-1)/2
2
Right-to-Left Binary Method

Processes the binary digits of the exponent from least significant to most significant.

result = 1
base = b % m
exponent = e
while exponent > 0:
  if exponent is odd: result = (result * base) % m
  exponent = exponent >> 1 (right shift)
  base = (base * base) % m
return result
3
Left-to-Right Binary Method

Processes the binary digits of the exponent from most significant to least significant.

result = 1
for each bit in binary representation of e (from left to right):
  result = (result * result) % m
  if current bit = 1: result = (result * b) % m
return result

Modular Arithmetic Properties

Property Formula Example
Modular Multiplication (a × b) mod m = [(a mod m) × (b mod m)] mod m (7 × 9) mod 5 = 3
Modular Exponentiation ab mod m = (a mod m)b mod m 73 mod 5 = 23 mod 5 = 3
Exponent Rules ab+c = ab × ac 23+4 = 23 × 24 = 8 × 16 = 128
Exponent Rules ab×c = (ab)c 23×2 = (23)2 = 82 = 64
Fermat's Little Theorem If p is prime and a not divisible by p: ap-1 ≡ 1 (mod p) 36 mod 7 = 1
Euler's Theorem If gcd(a, n) = 1: aφ(n) ≡ 1 (mod n) 56 mod 9 = 1 (φ(9)=6)

Applications in Cryptography

1
RSA Encryption

RSA uses modular exponentiation for both encryption and decryption:

Encryption: c = me mod n
Decryption: m = cd mod n
Where n = p × q (product of two large primes)
and e × d ≡ 1 (mod φ(n))
2
Diffie-Hellman Key Exchange

Allows two parties to establish a shared secret over an insecure channel:

1. Agree on public parameters: prime p and generator g
2. Alice sends A = ga mod p
3. Bob sends B = gb mod p
4. Shared secret: s = Ba mod p = Ab mod p = gab mod p
3
Digital Signatures (DSA/ECDSA)

Digital Signature Algorithm uses modular exponentiation for signature generation and verification:

Signature: (r, s) where
r = (gk mod p) mod q
s = k-1(H(m) + xr) mod q
Verification requires modular exponentiation

Calculator Features:

  • Uses fast binary exponentiation algorithm (O(log n) time complexity)
  • Handles large numbers efficiently using JavaScript BigInt
  • Visualizes the binary exponentiation process step-by-step
  • Shows binary representation of the exponent
  • Provides performance metrics and algorithm analysis
  • Includes common examples from cryptography and number theory

Frequently Asked Questions

For large exponents, the intermediate result be can be astronomically large (e.g., 123456 has over 900 digits). This would require enormous memory and computation time. Modular exponentiation algorithms compute the result modulo m without ever calculating the full exponentiation, making it efficient even for very large numbers.

Binary exponentiation has O(log e) time complexity, where e is the exponent. This is exponentially faster than the naive O(e) approach. Specifically, it requires at most 2·log₂(e) modular multiplications. For example, computing 71,000,000 mod 11 would require about 40 multiplications instead of 1,000,000.

Yes, the calculator uses JavaScript's BigInt type, which can handle arbitrarily large integers (limited by available memory). This allows computation with numbers having hundreds or thousands of digits, which is essential for cryptographic applications.

Regular exponentiation computes be as a potentially very large integer. Modular exponentiation computes be mod m, which is always between 0 and m-1. In modular exponentiation, we can apply properties of modular arithmetic to compute the result efficiently without calculating the full exponentiation.

Modular exponentiation forms the basis of public-key cryptography. In RSA, encryption and decryption are modular exponentiation operations. In Diffie-Hellman, key exchange relies on modular exponentiation. The "one-way" nature of modular exponentiation (easy to compute but hard to reverse without the private key) provides the security foundation.