gives the multiplicative order of k modulo n, defined as the smallest integer such that .
gives the generalized multiplicative order of k modulo n, defined as the smallest integer such that for some .
- MultiplicativeOrder is also known as modulo order or haupt‐exponent.
- Integer mathematical function, suitable for both symbolic and numerical manipulation.
- Typically used in modular arithmetic and cryptography.
- MultiplicativeOrder[k,n] gives the smallest positive integer m such that the remainder when dividing km by n is equal to 1.
- MultiplicativeOrder returns unevaluated if there is no integer satisfying the necessary conditions.
Examplesopen allclose all
Basic Examples (2)
The multiplicative order of 5 modulo 8:
Plot the sequence with a fixed modulus:
Plot the sequence, varying the modulus:
Numerical Manipulation (4)
Compute using integers:
Generalized multiplicative order:
Compute using large numbers:
Symbolic Manipulation (2)
Basic Applications (5)
Find all primitive roots modulo 43:
A rational number has a digit cycle of length if is prime and 10 is a primitive root for :
Compute MultiplicativeOrder using NestWhileList:
Count number of possible multiplicative orders modulo a given prime number:
The number of divisors of where is prime:
These are in fact the same list:
Number Theory (4)
The repetition period in Rule for odd divides q[n]:
The digits of in base repeat with period :
The function digitCycleLength gives the digit period for any rational number in base :
This shows that the decimal representation of in base 10 repeats every 3 digits:
Build an RSA-like toy encryption scheme:
Perform a cycling attack. One of the outputs will be the plaintext:
Properties & Relations (5)
The multiplicative order of a primitive root modulo n is EulerPhi[n]:
EulerPhi divides MultiplicativeOrder:
The result is always positive:
Find the smallest integer such that ≡ 2, 3, or 4 mod 7:
Find which of the remainders satisfies :
Solve the discrete log problem with :
Possible Issues (1)
For nonzero integers k and n, MultiplicativeOrder[k,n] exists if and only if k and n are coprime:
However, 10 and 22 are not coprime:
Neat Examples (2)
Visualize when a number has multiplicative order modulo 12:
Ulam spiral of MultiplicativeOrder: