PowerMod

Modular exponentiation: a^b mod m, computed without forming a^b directly.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaModular exponentiation↗WikidataQ1228841↗Wolfram LanguagePowerMod!↗Rosetta CodeModular exponentiation↗

PowerMod(a, b, m)modular exponentiation, $a^b \bmod m$.

SageMathenumeratio_power_mod(a, b, m)SymPypow(ZZ.convert(a), ZZ.convert(b), ZZ.convert(m))Oscarpowermod(ZZ(a), ZZ(b), ZZ(m))Juliapowermod(ZZ(a), ZZ(b), ZZ(m))Rustpowermod(a, b, m)

PowerMod(a, 1/r, m)the least $x \ge 0$ with $x^r \equiv a \pmod m$; more generally $s/r$ for $x^r \equiv a^s$

SageMathenumeratio_power_mod(a, 1/r, m)SymPypow(ZZ.convert(a), ZZ.convert(1/r), ZZ.convert(m))Oscarpowermod(ZZ(a), ZZ(1/r), ZZ(m))Juliapowermod(ZZ(a), ZZ(1/r), ZZ(m))Rustpowermod(a, 1/r, m)

PowerMod(u/v, b, m)a rational base, read in $\mathbb{Z}/m$ as $u \cdot v^{-1}$, a list of bases, and an exponent of 0 at any modulus

SageMathenumeratio_power_mod(u/v, b, m)SymPypow(ZZ.convert(u/v), ZZ.convert(b), ZZ.convert(m))Oscarpowermod(ZZ(u/v), ZZ(b), ZZ(m))Juliapowermod(ZZ(u/v), ZZ(b), ZZ(m))Rustpowermod(u/v, b, m)

Typed signatures

Type	Package	Applies
(integer, rational, integer) -> integer	compute-engine	always
(number, number, number) -> number	number-theoryreplaces residues	always
(number, number, number) -> number	residuesreplaces compute-engine	always

Domain: Modular arithmetic

Details

• Computed by repeated squaring, without ever forming $a^b$ directly -- efficient even for huge $b$.
• A negative $b$ gives the modular inverse of $a$ raised to $|b|$, when it exists.
• The inverse is undefined whenever $\gcd(a,m)\neq1$; compute-engine leaves such calls unevaluated.
• Equal to $\mathrm{Mod}(a^b, m)$ for positive $b$, just far more efficient. See Mod.
• A rational exponent $s/r$ gives the least $x$ with $x^r \equiv a^s$ — the first element of PowerModList — and stays unevaluated when there is none.
• Threads over lists in any argument.
• Gaussian integers are reduced as Mod reduces them; a rational-integer modulus must be positive, and a result that comes out real is reported in $[0, m)$.

Plot

Examples

32 more kept as data, checked against the oracles

Basic #

live ↗

In$\mathrm{PowerMod}(2, 10, 3)$Out$1$

live ↗

In$\mathrm{PowerMod}(3, 50, 11)$Out$1$

live ↗

In$\mathrm{PowerMod}(3, 2, 7)$Out$2$

A negative exponent gives the modular inverse

live ↗

In$\mathrm{PowerMod}(2, -1, 7)$Out$4$

Scope #

$3^{-1} \equiv 5$, and $5^2 = 25 \equiv 4$

live ↗

In$\mathrm{PowerMod}(3, -2, 7)$Out$4$

a square root of $3 \equiv 1 \pmod 2$

live ↗

In$\mathrm{PowerMod}(3, \frac{1}{2}, 2)$Out$1$

threads over a list of bases

live ↗

In$\mathrm{PowerMod}(\bigl\lbrack2, 3, 4\bigr\rbrack, 2, 5)$Out$\bigl\lbrack4, 4, 1\bigr\rbrack$

$a^0 = 1$ regardless of $a$ or $m$'s sign, so this is $\mathrm{Mod}(1, -14)$ even though $m<0$

live ↗

In$\mathrm{PowerMod}(-2, 0, -14)$Out$-13$

a rational exponent is a modular root: the least of $2, 5$

live ↗

In$\mathrm{PowerMod}(4, \frac{1}{2}, 7)$Out$2$

threads over lists; the period is the order of 2 mod 5

live ↗

In$\mathrm{PowerMod}(2, \bigl\lbrack10, 11, 12, 13, 14\bigr\rbrack, 5)$Out$\bigl\lbrack4, 3, 1, 2, 4\bigr\rbrack$

a 301-digit base

live ↗

In$\mathrm{PowerMod}(10^{300}+1, 7, 5)$Out$1$

a square root of 3 modulo the prime $10^{30} + 57$

live ↗

In$\mathrm{PowerMod}(3, \frac{1}{2}, 10^{30}+57)$Out$492\,767\,688\,934\,650\,018\,614\,948\,489\,645$

a rational base: $2 \cdot 3^{-1} = 2 \cdot 5 \equiv 3 \pmod 7$

live ↗

In$\mathrm{PowerMod}(\frac{2}{3}, 1, 7)$Out$3$

Gaussian integers: $(2+i)^2 = 3 + 4i \equiv i \pmod 3$

live ↗

In$\mathrm{PowerMod}(2+i, 2, 3)$Out$i$

a Gaussian modulus, and an exponent of $10^{30}$

live ↗

In$\mathrm{PowerMod}(1+2i, 10^{30}, 7+2i)$Out$1+2i$

$11 - 7i$ is a unit mod $7 + 4i$, so it has negative powers

live ↗

In$\mathrm{PowerMod}(11-7i, -4, 7+4i)$Out$-2-i$

Sum of squares mod $7$ over a residue range

live ↗

In$\sum_{a}^7\mathrm{PowerMod}(a, 2, 7)$Out$14$

live ↗

In$\mathrm{FindInstance}(\mathrm{PowerMod}(a, b, 17)=1∧0\lt a\lt17∧0\lt b\lt17, \bigl\lbrack a, b\bigr\rbrack, ℤ, 2)$Out$\bigl\lbrack\bigl\lbrack\mathrm{Rule}(a, 1), \mathrm{Rule}(b, 1)\bigr\rbrack, \bigl\lbrack\mathrm{Rule}(a, 1), \mathrm{Rule}(b, 2)\bigr\rbrack\bigr\rbrack$

Applications #

One step of RSA-style modular exponentiation: $7^{13} \bmod 33$

live ↗

In$\mathrm{PowerMod}(7, 13, 33)$Out$13$

$341 = 11 \cdot 31$ passes Fermat's test to base 2 — the least pseudoprime

live ↗

In$\mathrm{PowerMod}(2, 340, 341)$Out$1$

Diffie–Hellman: both parties reach the shared key $5^{6 \cdot 15} \bmod 23$

live ↗

In$\mathrm{PowerMod}(\mathrm{PowerMod}(5, 6, 23), 15, 23)=\mathrm{PowerMod}(\mathrm{PowerMod}(5, 15, 23), 6, 23)$Out$\mathrm{True}$

Properties #

By definition $a^b \bmod m$, computed without ever forming $a^b$ directly

live ↗

In$\mathrm{PowerMod}(2, 10, 3)=2^{10}\bmod3$Out$\mathrm{True}$

Euler's theorem: $a^{\varphi(m)} \equiv 1$ for $a$ coprime to $m$

live ↗

In$\mathrm{PowerMod}(7, \mathrm{Totient}(19), 19)$Out$1$

Congruent bases ($7\equiv12$) give the same power

live ↗

In$\bigl\lbrack\mathrm{PowerMod}(7, 2, 5), \mathrm{PowerMod}(12, 2, 5)\bigr\rbrack$Out$\bigl\lbrack4, 4\bigr\rbrack$

Same as reducing $2^3$ afterwards

live ↗

In$\bigl\lbrack\mathrm{PowerMod}(2, 3, 5), 8\bmod5\bigr\rbrack$Out$\bigl\lbrack3, 3\bigr\rbrack$

Exponent $-1$ gives the modular inverse

live ↗

In$\bigl\lbrack\mathrm{PowerMod}(2, -1, 5), \mathrm{ModularInverse}(2, 5)\bigr\rbrack$Out$\bigl\lbrack3, 3\bigr\rbrack$

Modulo 2, an even base gives $0$

live ↗

In$\bigl\lbrack2\mid8, \mathrm{PowerMod}(8, 3, 2)=0\bigr\rbrack$Out$\bigl\lbrack\mathrm{True}, \mathrm{True}\bigr\rbrack$

Euler: $a^{\varphi(n)}\equiv1$ for coprime $a$

live ↗

In$\mathrm{PowerMod}(7, \mathrm{Totient}(19), 19)=1$Out$\mathrm{True}$

Fermat: $2^{16}\equiv1 \pmod{17}$

live ↗

In$\mathrm{PowerMod}(2, 16, 17)$Out$1$

Threads over a list of bases

live ↗

In$\mathrm{PowerMod}(\bigl\lbrack5, -5\bigr\rbrack, 2, 3)$Out$\bigl\lbrack1, 1\bigr\rbrack$

Negative modulus: result stays unevaluated per element

live ↗

In$\mathrm{PowerMod}(\bigl\lbrack5, -5\bigr\rbrack, 2, -3)$Out$\bigl\lbrack\mathrm{PowerMod}(5, 2, -3), \mathrm{PowerMod}(-5, 2, -3)\bigr\rbrack$

Possible issues #

No inverse exists when $\gcd(a,m)\neq1$ (here $\gcd(2,4)=2$), so the call is left unevaluated

live ↗

In$\mathrm{PowerMod}(2, -1, 4)$Out$\mathrm{PowerMod}(2, -1, 4)$

A nonzero exponent with a negative modulus still declines, as in Wolfram, unlike the exponent-0 case above

live ↗

In$\mathrm{PowerMod}(-2, 3, -14)$Out$\mathrm{PowerMod}(-2, 3, -14)$

2 is not a square mod 5, so there is no root

live ↗

In$\mathrm{PowerMod}(2, \frac{1}{2}, 5)$Out$\mathrm{PowerMod}(2, \frac{1}{2}, 5)$

About

Examples	66
Checked against	Wolfram Language 60 agree6 differSageMath 48 agree2 differ6 unevaluated8 errorSymPy 29 agree1 differ7 unevaluated27 errorOscar 18 agreeJulia 22 agree42 errorRust 23 agree1 differ6 unevaluated7 error
Crosswalk	WikipediaWikidataWolfram LanguageSageMathSymPyOscarJuliaRustRosetta Code

Implementation

mappedoscarpackages/oracle/src/mappings.ts

mappedwolframpackages/oracle/src/mappings.ts

For a negative exponent and a Gaussian modulus m, Wolfram checks invertibility of a mod N(m) (a rational integer) rather than mod m itself, so it occasionally declines a case ours answers — e.g. PowerMod[11 - 7I, -4, 7 + 4I] errors since 11 - 7i shares a factor with N(7 + 4i) = 65, though gcd(11 - 7i, 7 + 4i) = 1.

mappedsagepackages/oracle/src/mappings.ts

Sage's power_mod takes a negative exponent, like ours; no rational base or exponent. The helper reduces into the sign of the modulus and runs over the Gaussian integers, where power_mod has no method.

mappedrustpackages/oracle/src/mappings.ts

Sage's power_mod takes a negative exponent, like ours; no rational base or exponent.

mappedsympypackages/oracle/src/mappings.ts

SymPy has no PowerMod function; this is Python's three-argument pow over SymPy's ZZ integers (pure-Python ones, as the runner pins), which takes a negative exponent through the modular inverse and gives the result the sign of the modulus, where ours declines a modulus below 1 unless the exponent is 0. The emit varies with the operands: a rational exponent s/r is the least root of x^r = a^s through nthroot_mod, as PowerModList (None where there is no root); a symbolic, rational or Gaussian operand goes to pow on SymPy numbers, which holds it (Mod((2 + I)**2, 3)) or ignores the modulus for a rational base. A list threads over whichever argument holds it.

mappedjuliapackages/oracle/src/mappings.ts

See also: Mod, PowerModList, ModularInverse