Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how

PowerMod

PowerMod[a,b,m]

gives a^b mod m.

PowerMod[a,-1,m]

finds the modular inverse of a modulo m.

PowerMod[a,1/r,m]

finds a modular r root of a.

Details

PowerMod is also known as modular exponentiation.
Mathematical function, suitable for both symbolic and numerical manipulation.
Typically used in modular arithmetic, cryptography, random number generation and cyclic operations in programs.
PowerMod[a,b,m] gives the remainder of a^b divided by m.

PowerMod[a,b,m] allows negative and rational values of b. It returns unevaluated if the corresponding modular inverse or root does not exist.
For positive b, PowerMod[a,b,m] gives the same result as Mod[a^b, m] but is much more efficient.

Examples

open allclose all

Basic Examples (3)

Compute mod 3:

Plot the sequence with fixed powers:

Plot the sequence with varying powers:

Scope (7)

Numerical Evaluation (4)

Compute using integers:

Rational exponent:

Gaussian integers:

Compute for large numbers:

PowerMod threads over lists:

TraditionalForm Formatting:

Symbolic Manipulation (3)

Use Reduce to simplify expressions:

Use FindInstance to find solutions to expressions containing PowerMod

Use PowerMod in a sum:

Applications (6)

Basic Applications (2)

Find a PrimitiveRoot of 9:

Use PowerMod to generate all coprime integers modulo 9:

Recognize base pseudoprimes:

Find all base 2 pseudoprimes below 1000:

Find all base 5 pseudoprimes below 1000:

Number Theory (4)

Build an RSA-like toy encryption scheme. Start with the modulus:

Find the universal exponent of the multiplication group modulo n:

Private key:

Public key:

Encrypt a message:

Decrypt it:

Build an RSA-like toy encryption scheme:

Perform a cycling attack. One of the outputs will be the plaintext:

Alice and Bob publicly agree on a prime number and a primitive root modulo that prime :

Then Alice and Bob each choose private keys:

Then Alice sends Bob mod while Bob sends Alice mod :

Bob then computes mod and Alice computes mod :

This is their secret number which they now both share:

Create a random number generator that uses the current time as a seed:

Choose a modulus and base:

Compute random numbers between and :

Properties & Relations (8)

PowerMod is a periodic function:

Determine PowerMod using Mod:

Determine ModularInverse:

If and , then :

If divides then :

if and are coprime:

Fermat's little theorem states that when is prime, then :

The results have the same sign as the modulus:

Possible Issues (1)

Modular square roots may not exist:

Neat Examples (3)

Plot a list of powers of 3 where the exponent is varied, modulo some prime number:

Plot values of varying powers of numbers with a fixed modulus:

Plot an Ulam spiral where numbers are colored based on PowerMod:

Top