• ← ModularInverse
• → Quotient

PowerMod

Modular exponentiation SymPy: mod_inverse, nth_root_mod, sqrt_mod, and Pow; WMA link.

PowerMod[x, y, m]

computes x^y modulo m.

PowerMod[x, -1, m]

computes modular inverse of x modulo m.

PowerMod[x, 1/r, m]

computes a module r-th root of x.

Compute 7 squared mod 5:

• • PowerMod[7, 2, 5]

PowerMod is periodic:

• • PowerMod[7 + 5, 2, 5]

Plot the sequence of PowerMod using varying powers:

• • DiscretePlot[PowerMod[m, 2, 11], {m, 1, 40}]

PowerMod can handle large integers:

• • PowerMod[2, 10000000, 3]

• • PowerMod[3, -2, 10]

PowerMod works on square roots:

• • PowerMod[3, 1/2, 2]

PowerMod works on nth roots other than a square root:

• • PowerMod[11, 1/3, 19]

When y is a root $1/r$, there may be more than one solution for PowerMod.
However, the result must satisfy $x^y = r$ mod m:

> x=11; r=3; m=19; Mod[(PowerMod[x, 1/r, m] ^ r), m] == x
= True

Note the inverse relationship PowerMod has when y is negative one:

• • PowerMod[3, -1, 11]

• • PowerMod[4, -1, 11]

Also, PowerMod with $-y$, is inverse of PowerMod with y:

• • PowerMod[3, -10, 11]  == PowerMod[PowerMod[3, 10, 11], 10, 11]

The first parameter, x should be invertible for modulus m:

• • PowerMod[0, -1, 2]

Also, you should not use zero as a modulus for y:

• • PowerMod[5, 2, 0]

PowerMod threads over lists

• • PowerMod[2, {10, 11, 12, 13, 14}, 5]