MultiplicativeOrder

The smallest positive k such that a^k ≡ 1 (mod n).

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaMultiplicative order↗MathWorldMultiplicativeOrder↗WikidataQ282723↗Wolfram LanguageMultiplicativeOrder!↗

MultiplicativeOrder(a, n)smallest positive $k$ with $a^k\equiv1\pmod n$.

SageMathMod(a, n).multiplicative_order()SymPyn_order(a, n)

MultiplicativeOrder(a, n, {r1, r2, …})smallest positive $k$ with $a^k \equiv r_i \pmod n$ for some $i$ — a discrete logarithm

MultiplicativeOrder(ResidueClass(a, n))the order of a unit of $\mathbb{Z}/n$

SageMathMod(a, n).multiplicative_order()SymPyn_order(a, n)

Typed signatures

Type	Package	Applies
(integer, integer, list<integer>?) -> integer	compute-engine	always
(value, integer?, list<integer>?) -> integer	residuesreplaces compute-engine	always

Domain: Modular arithmetic

Details

• Also called the modulo order; defined only when $\gcd(a,n)=1$, since otherwise no power of $a$ can reach 1 mod $n$.
• Always divides $\varphi(n)$, by Lagrange's theorem applied to the group of units mod $n$. See Totient.
• Unevaluated when no order exists.
• Computed from Carmichael's $\lambda(n)$ by stripping primes off it, so $n$ and each $p - 1$ must be factored.
• The three-argument form is a discrete logarithm, by Pohlig–Hellman over the order of $a$ and baby-step giant-step within each prime: the cost is $\sqrt q$ for the largest prime $q$ dividing that order — instant for a smooth order, hopeless for a safe prime.

Plot

argument a of type value has no control

Examples

3 more kept as data, checked against the oracles

Basic #

live ↗

In$\mathrm{MultiplicativeOrder}(5, 8)$Out$2$

live ↗

In$\mathrm{MultiplicativeOrder}(3, 7)$Out$6$

live ↗

In$\mathrm{MultiplicativeOrder}(5, 7)$Out$6$

$2^3=8\equiv1\pmod7$, and no smaller power works

live ↗

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

Scope #

a negative base: $-5 \equiv 2 \pmod 7$

live ↗

In$\mathrm{MultiplicativeOrder}(-5, 7)$Out$3$

the first power of 5 to reach 3 or $11 \equiv 4$: $5^2 = 25 \equiv 4$

live ↗

In$\mathrm{MultiplicativeOrder}(5, 7, \bigl\lbrack3, 11\bigr\rbrack)$Out$2$

a 10 001-digit base modulo the prime 7919

live ↗

In$\mathrm{MultiplicativeOrder}(10^{10\,000}, 7\,919)$Out$3\,959$

the first power of 3 to reach $\pm 1$: $3^3 = 27 \equiv -1$

live ↗

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

$5^2 = 25 \equiv 4$

live ↗

In$\mathrm{MultiplicativeOrder}(5, 7, \bigl\lbrack2, 3, 4\bigr\rbrack)$Out$2$

a discrete log mod the Mersenne prime $2^{61} - 1$, whose $p - 1$ is smooth

live ↗

In$\mathrm{MultiplicativeOrder}(3, 2^{61}-1, \bigl\lbrack2\bigr\rbrack)$Out$159\,602\,976\,958\,324\,900$

3 has order $(p-1)/3$ modulo $2^{127} - 1$

live ↗

In$\mathrm{MultiplicativeOrder}(3, 2^{127}-1)$Out$56\,713\,727\,820\,156\,410\,577\,229\,101\,238\,628\,035\,242$

Properties #

1 is the only element of order 1

live ↗

In$\mathrm{MultiplicativeOrder}(1, 7)$Out$1$

The multiplicative order always divides $\varphi(n)$. See Totient

live ↗

In$\mathrm{Totient}(7)\bmod\mathrm{MultiplicativeOrder}(3, 7)=0$Out$\mathrm{True}$

the discrete log inverts PowerMod

live ↗

In$\mathrm{PowerMod}(3, \mathrm{MultiplicativeOrder}(3, 2^{61}-1, \bigl\lbrack2\bigr\rbrack), 2^{61}-1)$Out$2$

The order always divides $\varphi(n)$

live ↗

In$\mathrm{MultiplicativeOrder}(5, 12)\mid\mathrm{Totient}(12)$Out$\mathrm{True}$

$5\equiv2$ and $2^2\equiv1 \pmod3$

live ↗

In$\mathrm{MultiplicativeOrder}(5, 3)$Out$2$

$-5\equiv1 \pmod3$ has order $1$

live ↗

In$\mathrm{MultiplicativeOrder}(-5, 3)$Out$1$

With target residue $4$: least $k$ with $5^k\equiv4 \pmod 7$

live ↗

In$\mathrm{MultiplicativeOrder}(5, 7, \bigl\lbrack4\bigr\rbrack)$Out$2$

live ↗

In$\mathrm{MultiplicativeOrder}(\mathrm{PrimitiveRoot}(109), 109)=\mathrm{Totient}(109)$Out$\mathrm{True}$

Possible issues #

No order exists when $\gcd(a,n)\neq1$; here $\gcd(10,22)=2$, so compute-engine leaves it unevaluated

live ↗

In$\mathrm{MultiplicativeOrder}(10, 22)$Out$\mathrm{MultiplicativeOrder}(10, 22)$

3 is not a power of 2 mod 7 — the powers are $\{1, 2, 4\}$

live ↗

In$\mathrm{MultiplicativeOrder}(2, 7, \bigl\lbrack3\bigr\rbrack)$Out$\mathrm{MultiplicativeOrder}(2, 7, \bigl\lbrack3\bigr\rbrack)$

$10^6\equiv1 \pmod{21}$

live ↗

In$\mathrm{MultiplicativeOrder}(10, 21)$Out$6$

$21\equiv1 \pmod{10}$, so order $1$; argument order matters

live ↗

In$\mathrm{MultiplicativeOrder}(21, 10)$Out$1$

About

Examples	26
Checked against	Wolfram Language 22 agree2 differ2 errorSageMath 16 agree1 errorSymPy 13 agree4 error
Crosswalk	WikipediaMathWorldWikidataWolfram LanguageSageMathSymPy

Implementation

mappedsagepackages/oracle/src/mappings.ts

mappedsympypackages/oracle/src/mappings.ts

n_order raises where gcd(a, n) is not 1, as ours stays unevaluated. The three-argument discrete logarithm over a list of targets has no one-call SymPy form (discrete_log takes one target).

See also: PowerMod