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^(th) 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:

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:

Introduced in 1988
 (1.0)