# PowerMod

PowerMod[a,b,m]

gives ab 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 ab 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 Manipulation(4)

Compute using integers:

Rational exponent:

Gaussian integers:

Compute for large numbers:

### 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)

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: