WOLFRAM

Wolfram Language & System Documentation Center

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
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Numerical Evaluation  
Symbolic Manipulation  
Applications  
Basic Applications  
Number Theory  
Properties & Relations  
Possible Issues  
Neat Examples  
See Also
Tech Notes
Related Guides
Related Links
History
Cite this Page

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 all close all

Basic Examples  (3)

Compute mod 3:

Wolfram Language code: PowerMod[2, 10, 3]

Plot the sequence with fixed powers:

Wolfram Language code: DiscretePlot[PowerMod[m, 2, 11], {m, 1, 50}]

Plot the sequence with varying powers:

Wolfram Language code: DiscretePlot[PowerMod[3, b, 11], {b, 1, 50}]

Scope  (7)

Numerical Evaluation  (4)

Compute using integers:

Wolfram Language code: PowerMod[3, 2, 7]
Wolfram Language code: PowerMod[3, -2, 7]

Rational exponent:

Wolfram Language code: PowerMod[3, 1 / 2, 2]

Gaussian integers:

Wolfram Language code: PowerMod[2 + I, 2, 3]

Compute for large numbers:

Wolfram Language code: PowerMod[10 ^ 300 + 1, 7, 5]

PowerMod threads over lists:

Wolfram Language code: PowerMod[2, {10, 11, 12, 13, 14}, 5]

TraditionalForm Formatting:

Wolfram Language code: TraditionalForm[PowerMod[a, b, m]]

Symbolic Manipulation  (3)

Use Reduce to simplify expressions:

Wolfram Language code: Reduce[PowerMod[a, 2, 17] == 2 && 0 < a < 17, a, Integers]

Use FindInstance to find solutions to expressions containing PowerMod

Wolfram Language code: FindInstance[PowerMod[a, b, 17] == 1 && 0 < a < 17 && 0 < b < 17, {a, b}, Integers, 2]

Use PowerMod in a sum:

Wolfram Language code: Sum[PowerMod[a, 2, 7], {a, 7}]

Applications  (6)

Basic Applications  (2)

Find a PrimitiveRoot of 9:

Wolfram Language code: PrimitiveRoot[9]

Use PowerMod to generate all coprime integers modulo 9:

Wolfram Language code: Union[Table[PowerMod[%, b, 9], {b, 10}]]

Recognize base pseudoprimes:

Wolfram Language code: BPseudoPrimeQ[b_, n_] := PowerMod[b, n - 1, n] == 1 && CompositeQ[n]

Find all base 2 pseudoprimes below 1000:

Wolfram Language code: Select[Range[1000], BPseudoPrimeQ[2, #]&]

Find all base 5 pseudoprimes below 1000:

Wolfram Language code: Select[Range[1000], BPseudoPrimeQ[5, #]&]

Number Theory  (4)

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

Wolfram Language code: {p, q} = Prime[RandomInteger[{10 ^ 4, 10 ^ 5}, {2}]]; n = p q

Find the universal exponent of the multiplication group modulo n:

Wolfram Language code: λ = CarmichaelLambda[n]

Private key:

Wolfram Language code: d = NestWhile[#1 + 1&, Round[n / 3], GCD[λ, #1] =!= 1&]

Public key:

Wolfram Language code: e = PowerMod[d, -1, λ]

Encrypt a message:

Wolfram Language code: PowerMod[ToCharacterCode["RSA in Mathematica"], e, n]

Decrypt it:

Wolfram Language code: FromCharacterCode[PowerMod[%, d, n]]

Build an RSA-like toy encryption scheme:

Wolfram Language code: {p, q} = {47, 59}; n = p q; ϕ = EulerPhi[n]; d = NestWhile[#1 + 1&, Round[n / 3], GCD[ϕ, #1] =!= 1&]; e = 17; PlainText = 1504; CypherText = PowerMod[PlainText, e, n];

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

Wolfram Language code: Cy[1] = PowerMod[CypherText, e, n]; Cy[j_] := PowerMod[Cy[j - 1], e, n]; Table[Cy[i], {i, Divisors[MultiplicativeOrder[e, ϕ]]}]

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

Wolfram Language code: p = RandomPrime[10 ^ 50];
Wolfram Language code: g = PrimitiveRoot[p];

Then Alice and Bob each choose private keys:

Wolfram Language code: {a, b} = RandomInteger[p, {2}];

Then Alice sends Bob mod while Bob sends Alice mod :

Wolfram Language code: A = PowerMod[g, a, p];
Wolfram Language code: B = PowerMod[g, b, p];

Bob then computes mod and Alice computes mod :

Wolfram Language code: AlicesKey = PowerMod[A, b, p]
Wolfram Language code: BobsKey = PowerMod[B, a, p]

This is their secret number which they now both share:

Wolfram Language code: AlicesKey == BobsKey

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

Wolfram Language code: x[0] = UnixTime[] x[k_] := Mod[PowerMod[a, k, m]x[0], m];

Choose a modulus and base:

Wolfram Language code: m = 2147483647; a = 16807;

Compute random numbers between and :

Wolfram Language code: Histogram[Table[x[i] / m, {i, 0, 1000}], 10]

Properties & Relations  (8)

PowerMod is a periodic function:

Wolfram Language code: {PowerMod[7, 2, 5], PowerMod[7 + 5, 2, 5]}

Determine PowerMod using Mod:

Wolfram Language code: {PowerMod[2, 3, 5], Mod[2 ^ 3, 5]}

Determine ModularInverse:

Wolfram Language code: {PowerMod[2, -1, 5], ModularInverse[2, 5]}

If and , then :

Wolfram Language code: Mod[5, 3] == Mod[2, 3]
Wolfram Language code: Mod[2, 3] == Mod[8, 3]
Wolfram Language code: Mod[8, 3] == Mod[5, 3]

If divides then :

Wolfram Language code: {Divisible[8, 2], PowerMod[8, 3, 2] == 0}

if and are coprime:

Wolfram Language code: PowerMod[7, EulerPhi[19], 19] == 1

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

Wolfram Language code: PowerMod[2, 17 - 1, 17]

The results have the same sign as the modulus:

Wolfram Language code: PowerMod[{5, -5}, 2, 3]
Wolfram Language code: PowerMod[{5, -5}, 2, -3]

Possible Issues  (1)

Modular square roots may not exist:

Wolfram Language code: PowerMod[2, 1 / 2, 5]

Neat Examples  (3)

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

Wolfram Language code: ListPlot[Table[PowerMod[3, b, Prime[44]], {b, 1, Prime[44] - 1}], Filling -> Axis]

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

Wolfram Language code: ArrayPlot[Table[PowerMod[a, b, 32], {a, 2, 100}, {b, 2, 100}], ColorFunction -> "Rainbow"]

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

Wolfram Language code: ulamSpiral[n_] := Permute[Range[n ^ 2], Accumulate@Take[Join[{n ^ 2 + 1} / 2, Flatten@Table [(-1) ^ j i, {j, n}, {i, {-1, n}}, {j}]], n ^ 2]]~Partition~n ArrayPlot[PowerMod[ulamSpiral[101], 3, 17], ColorFunction -> "Rainbow"]
Wolfram Research (1988), PowerMod, Wolfram Language function, https://reference.wolfram.com/language/ref/PowerMod.html.

Text

Wolfram Research (1988), PowerMod, Wolfram Language function, https://reference.wolfram.com/language/ref/PowerMod.html.

CMS

Wolfram Language. 1988. "PowerMod." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/PowerMod.html.

APA

Wolfram Language. (1988). PowerMod. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/PowerMod.html

BibTeX

@misc{reference.wolfram_2026_powermod, author="Wolfram Research", title="{PowerMod}", year="1988", howpublished="\url{https://reference.wolfram.com/language/ref/PowerMod.html}", note=[Accessed: 12-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_powermod, organization={Wolfram Research}, title={PowerMod}, year={1988}, url={https://reference.wolfram.com/language/ref/PowerMod.html}, note=[Accessed: 12-June-2026]}