Modular Exponentiation (PowMod)

Calculator and formula for computing modular exponentiation (PowMod)

Modular exponentiation calculator

What is calculated?

This function returns the result of the Modular Exponentiation (PowMod). The result is the remainder of a division of b^e by m, computed as (b^e) mod m.

Input values




Result
The result is the remainder of dividing b^e by m

Modular exponentiation info

Properties

Modular exponentiation:

  • Computes (b^e) mod m efficiently
  • Avoids large intermediate results
  • Result always between 0 and m-1
  • Important in cryptography

Note: Base b and modulo m must be positive integers. Exponent e can be 0.

Examples
3² mod 5 = 4
9 mod 5 = 4
2³ mod 7 = 1
8 mod 7 = 1
5⁴ mod 11 = 9
625 mod 11 = 9
7⁰ mod 10 = 1
Any number to the power 0 is 1
Applications
  • RSA encryption
  • Diffie-Hellman key exchange
  • Digital signatures
  • Pseudorandom number generation


Formulas of modular exponentiation

Basic formula
\[x = b^e \bmod m\] Modular exponentiation
Equivalent form
\[x = (b^e) \bmod m\] Remainder of division
Multiplication rule
\[(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m\] Product modulo m
Power rule
\[a^{x+y} \bmod m = (a^x \bmod m \cdot a^y \bmod m) \bmod m\] Exponent addition
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

Calculation example

Example: calculate 4² mod 10

Given:

  • Base b = 4
  • Exponent e = 2
  • Modulo m = 10

Calculation:

\[4^2 \bmod 10 = 16 \bmod 10 = 6\]

Result: The remainder of 16 ÷ 10 is 6.

RSA encryption example

Simplified RSA example

RSA parameters:

  • p = 3, q = 11 (primes)
  • n = p·q = 33
  • φ(n) = (p-1)·(q-1) = 20
  • e = 3 (public exponent)

Encrypting m = 4:

\[c = m^e \bmod n\] \[c = 4^3 \bmod 33 = 64 \bmod 33 = 31\]

Result: Message 4 is encrypted to 31.

Fast exponentiation

Example: 5¹³ mod 13 using binary method

Binary representation:

13 = 1101₂ = 8 + 4 + 1

5¹³ = 5⁸ · 5⁴ · 5¹

Stepwise calculation:

5¹ mod 13 = 5
5² mod 13 = 12
5⁴ mod 13 = 1
5⁸ mod 13 = 1
5¹³ mod 13 = 1·1·5 = 5

Advantage: Only log₂(13) ≈ 4 multiplications instead of 12.

Definition and applications

What is modular exponentiation?

Modular exponentiation computes (b^e) mod m efficiently without explicitly calculating the often very large number b^e. This is essential for cryptographic applications that use large numbers.

Cryptographic significance

In modern cryptography modular exponentiation underpins: RSA encryption, Diffie-Hellman key exchange, digital signatures, and many other security schemes.

Algorithmic efficiency
  • Naive method: O(e) multiplications
  • Binary method: O(log e) multiplications
  • Memory advantage: No large intermediate results
  • Practical: Usable for very large exponents




More Exp, Log and Root functions

Exponential function base 10x  •  Exponential function base ex  •  Exponential function base xy  •  Modular Exponentiation (PowMod)  •  Logarithm to base 10 (Log)  •  Logarithm to base e (Ln)  •  Logarithm to base a (Loga)  •  Square root (sqrt)  •  Cubic root (cbrt)  •  nth root  •  Hypot  •