Multiplicative Order

The multiplicative order of $ a $ modulo $ n $ is the smallest strictly positive integer $ k $ such that $ a^k \equiv 1 \pmod{n} $.

The multiplicative order measures the length of the cycle traced by a number raised to its successive powers modulo another number. Raising an integer $ a $ to successive powers modulo an integer $ n $ will always eventually return to 1, provided that $ a $ and $ n $ are coprime. The powers $ a^1, a^2, a^3, \ldots $ describe a closed cycle in the set of residues modulo $ n $, and the order is the length of this cycle: it is the arithmetic analogue of the period of a periodic function.

Let $ n \geq 2 $ and $ a $ be an integer invertible modulo $ n $, i.e. coprime to $ n $. The multiplicative order of $ a $ modulo $ n $, denoted $ \operatorname{ord}_n(a) $, is defined by $ \operatorname{ord}_n(a) = \min\{k \in \mathbb{N}^* : a^k \equiv 1 \pmod{n}\} $.

If $ a $ and $ n $ share a common factor, then $ a^k $ remains divisible by that factor for every $ k $, and $ a^k \bmod n $ is never 1: the order does not exist. Conversely, the condition $ \gcd(a, n) = 1 $ guarantees that $ a $ has an inverse modulo $ n $, and Fermat's little theorem as well as Euler's theorem ensure that $ a^{\varphi(n)} \equiv 1 \pmod{n} $: the set of valid exponents is therefore never empty, and a minimum always exists.

This is a direct consequence of Lagrange's theorem: in a finite group, the order of an element divides the order of the group.

Now the group $ (\mathbb{Z}/n\mathbb{Z})^* $ has exactly $ \varphi(n) $ elements, where $ \varphi $ is Euler's totient function.

Thus $ \operatorname{ord}_n(a) $ divides $ \varphi(n) $.

Note: The order also divides the value $ \lambda(n) $ of the Carmichael function, which is the smallest universal exponent annihilating all elements of the group.

When $ \operatorname{ord}_n(a) = \varphi(n) $, the element $ a $ alone traverses the entire group of units: $ a $ is a primitive root (or generator) modulo $ n $, and the group is cyclic.

In other words, the powers of $ a $ generate all invertible elements, each exactly once per cycle.

The algorithm can be summarized as:

function multiplicative_order(a, n)

if gcd(a, n) ≠ 1 → return "order undefined"

e ← φ(n) # via factorization of n

factor e = ∏ p_i^{e_i} # factorization of φ(n)

for each prime factor p of e →

while e mod p = 0 and a^(e/p) ≡ 1 (mod n) :

e ← e / p

return e

Or in Python code: def multiplicative_order(a, n):

if math.gcd(a, n) != 1:

return None

e = phi(n)

for p in prime_factors(e):

while e % p == 0 and pow(a, e // p, n) == 1:

e //= p

return e

The discrete logarithm is the inverse problem of exponentiation: given $ g $ and $ g^x \bmod p $, find $ x $.

The multiplicative order is the safeguard of several protocols.

For RSA: if the encryption exponent shared a small order with certain messages, short cycles would appear and make the ciphertext predictable; security implicitly assumes large and poorly known orders.

For the Diffie-Hellman key exchange: security relies on a generator of large prime order, choosing a small-order subgroup would make it possible to steal secrets.

For ElGamal and DSA: same requirements, the order of the generator must be a large prime, often a prime divisor $ q $ of $ p - 1 $.

Overall, a golden rule: any element of small order is a cryptographic flaw.