PowerModList

Every $x$ in $[0, m)$ with $x^r \equiv a^s \pmod m$ — all the values $a^{s/r}$ can take modulo $m$.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguagePowerModList!↗

PowerModList(a, s/r, m)every $x$ in $[0, m)$ with $x^r \equiv a^s \pmod m$, ascending

SageMathenumeratio_power_mod_list(a, s/r, m)SymPynthroot_mod(pow(ZZ.convert(a), S(s/r).p, ZZ.convert(m)), S(s/r).q, m, True)

PowerModList(a, k, m)an integer exponent gives the single value $\{a^k \bmod m\}$

SageMathenumeratio_power_mod_list(a, k, m)SymPynthroot_mod(pow(ZZ.convert(a), S(k).p, ZZ.convert(m)), S(k).q, m, True)

PowerModList(a, -1, m)the modular inverse $\{a^{-1}\}$, or $\{\}$ when $\gcd(a, m) \ne 1$

SageMathenumeratio_power_mod_list(a, -1, m)SymPynthroot_mod(pow(ZZ.convert(a), S(-1).p, ZZ.convert(m)), S(-1).q, m, True)

Typed signatures

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

Domain: Modular arithmetic

Details

• The problem splits over the prime powers of $m$ by the Chinese remainder theorem: a root mod $m$ is one root per channel $p^e$, every combination, so the count is the product of the channel counts.
• Mod a prime $p$ the units are cyclic of order $p - 1$, so $x^r \equiv b$ has exactly $\gcd(r, p-1)$ roots or none. One root is built Sylow subgroup by Sylow subgroup — only the primes dividing $r$ need a discrete log — so $p - 1$ is never factored and a 30-digit prime costs a millisecond.
• Roots are Hensel-lifted up each prime power: a root with $r x^{r-1} \not\equiv 0 \pmod p$ lifts uniquely; a singular one (the 2-adic channel of a square root, or $p \mid x$) lifts to all $p$ of its lifts or to none.
• The modulus has to be factored, by trial division and Pollard's rho under a step budget. A product of two large primes is out of reach, and the call stays unevaluated — which is the whole security of the Rabin cryptosystem.
• At most 100 000 roots are listed; past that the call stays unevaluated rather than build the list.
• Beyond Wolfram, a rational $a = u/v$ with $\gcd(v, m) = 1$ is read in $\mathbb{Z}/m$ as $u \cdot v^{-1}$, the image of $\mathbb{Z}_{(m)}$; a denominator sharing a factor with $m$ has no image, and the list is empty. See RationalReconstruction for the way back.
• Threads over lists in any argument.
• Over the Gaussian integers — beyond Wolfram, whose PowerModList takes integers only — $m$ factors into Gaussian prime powers: a split prime maps onto $\mathbb{Z}/p^e$ by $i \mapsto \sqrt{-1}$, an inert $p$ has residue field $\mathbb{F}_{p^2}$ and lifts by Hensel, and $1 + i$ lifts by testing both residues.

Examples

7 more kept as data, checked against the oracles

Basic #

the square roots of 3 modulo 11: $5^2 = 25$ and $6^2 = 36$ are both $\equiv 3$

live ↗

In$\mathrm{PowerModList}(3, \frac{1}{2}, 11)$Out$\bigl\lbrack5, 6\bigr\rbrack$

the cube roots of unity modulo 7, since $3 \mid 6$

live ↗

In$\mathrm{PowerModList}(1, \frac{1}{3}, 7)$Out$\bigl\lbrack1, 2, 4\bigr\rbrack$

an integer exponent is an ordinary power: $2^{10} = 1024$

live ↗

In$\mathrm{PowerModList}(2, 10, 1\,000)$Out$\bigl\lbrack24\bigr\rbrack$

Scope #

a general exponent $s/r$: every $x$ with $x^2 \equiv 2^3$

live ↗

In$\mathrm{PowerModList}(2, \frac{3}{2}, 17)$Out$\bigl\lbrack5, 12\bigr\rbrack$

the three cube roots of $2^2 = 4$, since $3 \mid 30$

live ↗

In$\mathrm{PowerModList}(2, \frac{2}{3}, 31)$Out$\bigl\lbrack16, 18, 28\bigr\rbrack$

exponent $-1$ is the modular inverse: $3 \cdot 5 = 15 \equiv 1$

live ↗

In$\mathrm{PowerModList}(3, -1, 7)$Out$\bigl\lbrack5\bigr\rbrack$

a prime power: the root $2$ of $x^2 \equiv -1 \pmod 5$, Hensel-lifted to $5^4$

live ↗

In$\mathrm{PowerModList}(-1, \frac{1}{2}, 625)$Out$\bigl\lbrack182, 443\bigr\rbrack$

a rational base reads as $2 \cdot 3^{-1}$ in $\mathbb{Z}/23$

live ↗

In$\mathrm{PowerModList}(\frac{2}{3}, \frac{1}{2}, 23)$Out$\bigl\lbrack4, 19\bigr\rbrack$

threads over lists: the squares mod 5 are exactly 1 and 4

live ↗

In$\mathrm{PowerModList}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack, \frac{1}{2}, 5)$Out$\bigl\lbrack\bigl\lbrack1, 4\bigr\rbrack, \bigl\lbrack\bigr\rbrack, \bigl\lbrack\bigr\rbrack, \bigl\lbrack2, 3\bigr\rbrack\bigr\rbrack$

$\sqrt{-1}$ modulo the 31-digit prime $10^{30} + 57$ — no scan, no factoring of $p - 1$

live ↗

In$\mathrm{PowerModList}(-1, \frac{1}{2}, 10^{30}+57)$Out$\bigl\lbrack164\,543\,371\,520\,667\,882\,579\,352\,850\,009, 835\,456\,628\,479\,332\,117\,420\,647\,150\,048\bigr\rbrack$

the cube roots of 2 modulo the Mersenne prime $2^{89} - 1$; the first is $2^{30}$, since $2^{90} = 2 \cdot 2^{89} \equiv 2$

live ↗

In$\mathrm{PowerModList}(2, \frac{1}{3}, 2^{89}-1)$Out$\bigl\lbrack1\,073\,741\,824, 205\,880\,356\,524\,696\,485\,265\,270\,985, 413\,089\,663\,117\,993\,651\,110\,549\,302\bigr\rbrack$

forty Hensel steps up from $\sqrt{-1} \equiv 2 \pmod 5$

live ↗

In$\mathrm{PowerModList}(-1, \frac{1}{2}, 5^{40})$Out$\bigl\lbrack2\,224\,618\,918\,409\,236\,552\,857\,702\,057, 6\,870\,328\,099\,320\,045\,826\,292\,688\,568\bigr\rbrack$

the square roots of 1 modulo the product of the first 16 primes: one per $\pm$ sign over the 15 odd channels, $2^{15}$

live ↗

In$\mathrm{Length}(\mathrm{PowerModList}(1, \frac{1}{2}, 2×3×5×7×11×13×17×19×23×29×31×37×41×43×47×53))$Out$32\,768$

the 1000th roots of unity mod $2^{61} - 1$: $\gcd(1000, 2^{61} - 2) = 50$ of them

live ↗

In$\mathrm{Length}(\mathrm{PowerModList}(1, \frac{1}{1\,000}, 2^{61}-1))$Out$50$

a square root of $i$ in $\mathbb{Z}[i]/(7)$, the field of 49 elements: $(2 + 2i)^2 = 8i \equiv i$

live ↗

In$\mathrm{PowerModList}(i, \frac{1}{2}, 7)$Out$\bigl\lbrack-2-2i, 2+2i\bigr\rbrack$

$10^{20} + 39$ is inert, so its residue field is $\mathbb{F}_{p^2}$ with $p$ of 21 digits

live ↗

In$\mathrm{PowerModList}(3+4i, \frac{1}{2}, 10^{20}+39)$Out$\bigl\lbrack-2-i, 2+i\bigr\rbrack$

Applications #

the split units of $\mathbb{Z}/15$: $j_1 \mapsto 4$ is a ring homomorphism $\mathbb{R}[j]/(j^2 - 1) \to \mathbb{Z}/15$

live ↗

In$\mathrm{PowerModList}(1, \frac{1}{2}, 15)$Out$\bigl\lbrack1, 4, 11, 14\bigr\rbrack$

so the identity $(1+j)(1-j) = 0$ transports by $j \mapsto 4$

live ↗

In$(1+4)(1-4)\bmod15$Out$0$

imaginary units of $\mathbb{Z}/65$ exist because $5$ and $13$ are both $\equiv 1 \pmod 4$

live ↗

In$\mathrm{PowerModList}(-1, \frac{1}{2}, 65)$Out$\bigl\lbrack8, 18, 47, 57\bigr\rbrack$

Rabin decryption: knowing the factors of $n$, the four square roots of the ciphertext include the message

live ↗

In$\mathrm{PowerModList}(\mathrm{PowerMod}(123\,456\,789, 2, 1\,000\,003×1\,000\,033), \frac{1}{2}, 1\,000\,003×1\,000\,033)$Out$\bigl\lbrack123\,456\,789, 30\,305\,547\,335, 969\,730\,452\,764, 999\,912\,543\,310\bigr\rbrack$

Properties #

mod a prime there are exactly $\gcd(r, p - 1)$ $r$-th roots of unity

live ↗

In$\mathrm{Length}(\mathrm{PowerModList}(1, \frac{1}{12}, 1\,009))=\gcd(12, 1\,008)$Out$\mathrm{True}$

for odd $m$ the square roots of 1 are the $2^{\omega(m)}$ sign vectors over the CRT channels: $1155 = 3 \cdot 5 \cdot 7 \cdot 11$

live ↗

In$\mathrm{Length}(\mathrm{PowerModList}(1, \frac{1}{2}, 1\,155))=2^{\mathrm{PrimeNu}(1\,155)}$Out$\mathrm{True}$

PowerMod with a rational exponent is the least element of the list

live ↗

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

Possible issues #

the cubes mod 7 are only $0, 1, 6$, so 2 has no cube root

live ↗

In$\mathrm{PowerModList}(2, \frac{1}{3}, 7)$Out$\bigl\lbrack\bigr\rbrack$

no square root of $-1$: $3 \equiv 3 \pmod 4$ blocks its channel

live ↗

In$\mathrm{PowerModList}(-1, \frac{1}{2}, 15)$Out$\bigl\lbrack\bigr\rbrack$

no inverse when $\gcd(a, m) \ne 1$, so the list is empty

live ↗

In$\mathrm{PowerModList}(2, -1, 4)$Out$\bigl\lbrack\bigr\rbrack$

the 2-adic channel breaks the $2^{\omega(m)}$ law: $\mathbb{Z}/2^a$ has four square roots of 1 for $a \ge 3$

live ↗

In$\mathrm{PowerModList}(1, \frac{1}{2}, 8)$Out$\bigl\lbrack1, 3, 5, 7\bigr\rbrack$

a product of two 21-digit primes cannot be factored in budget, so even $\sqrt 4$ stays unevaluated — finding the other two roots is as hard as factoring

live ↗

In$\mathrm{PowerModList}(4, \frac{1}{2}, (10^{20}+39)(10^{20}+129))$Out$\mathrm{PowerModList}(4, \frac{1}{2}, 10\,000\,000\,000\,000\,000\,016\,800\,000\,000\,000\,000\,005\,031)$

$x^2 \equiv 0 \pmod{3^{40}}$ has $3^{20}$ roots — too many to list

live ↗

In$\mathrm{PowerModList}(0, \frac{1}{2}, 3^{40})$Out$\mathrm{PowerModList}(0, \frac{1}{2}, 12\,157\,665\,459\,056\,928\,801)$

Neat examples #

the moduli with four or more square roots of 1 come in patterns: mod 24 every unit is one, since $(\mathbb{Z}/24)^\times \cong C_2^3$

live ↗

In$\mathrm{PowerModList}(1, \frac{1}{2}, \bigl\lbrack8, 15, 21, 24\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack1, 3, 5, 7\bigr\rbrack, \bigl\lbrack1, 4, 11, 14\bigr\rbrack, \bigl\lbrack1, 8, 13, 20\bigr\rbrack, \bigl\lbrack1, 5, 7, 11, 13, 17, 19, 23\bigr\rbrack\bigr\rbrack$

About

Examples	37
Checked against	Wolfram Language 26 agree10 differ1 errorSageMath 25 agree1 differ9 errorSymPy 26 agree1 differ9 errormathlib4 1 agreeOscar 1 agreeJulia 1 agreeRust 1 agree
Crosswalk	Wolfram LanguageSageMathSymPy

Implementation

mappedwolframpackages/oracle/src/mappings.ts

Sage reaches this through Zmod(m)(a).nth_root(b, all=True) (run.ts's SAGE_PREAMBLE); no one-liner in SymPy.

mappedsagepackages/oracle/src/mappings.ts

Sage reaches this through Zmod(m)(a).nth_root(b, all=True) (run.ts's SAGE_PREAMBLE); no one-liner in SymPy.

mappedsympypackages/oracle/src/mappings.ts

x^r = a^s (mod m) is nthroot_mod's x^n = a (mod p) with n = r and a = pow(a, s, m) over ZZ, which takes a negative s through the modular inverse. SymPy takes integer residues, so a rational or Gaussian base is an error there. A list threads over the base only.

See also: PowerMod, ModularInverse, MultiplicativeOrder, PrimitiveRootList, RationalReconstruction