Engineering / Mathematics — Abelian Groups
The Order of a Group Element
The order of an element, its relationship to the group order, and the computational cost of determining it.
Executive summary
The order of an element is the smallest positive power returning the identity. It divides the group order, which is the single most useful fact about finite groups.
Computing the order of an element requires the factorisation of the group order, which is why cryptographic groups are constructed with that factorisation known in advance.
Learning objectives
- Define element order and prove it divides the group order.
- Compute an element's order given the factorisation of the group order.
- Explain why the factorisation is required.
01Definition and divisibility
Order of an element
The order of a ∈ G is the least positive integer k with a^k = e, written ord(a). In a finite group it always exists.
Order divides group order
For finite G, ord(a) divides |G|, and consequently a^{|G|} = e for every a ∈ G.
This is Lagrange's theorem applied to the subgroup generated by a, which has exactly ord(a) elements. Fermat's little theorem and Euler's theorem are both immediate corollaries, taking G to be the units modulo a prime or modulo n.
a^k = e ⇔ ord(a) divides k02Computing the order
Testing every exponent is exponential. The efficient method uses the divisibility fact: the order divides |G|, so it is found by removing prime factors one at a time.
Order of an element
element a, group order |G| with its factorisationord(a)- Factor the group order as |G| = ∏ pᵢ^{eᵢ}. This factorisation must be known.
- Set k = |G|.
- For each prime pᵢ dividing |G|:
- While pᵢ divides k and a^{k/pᵢ} = e, set k = k/pᵢ.
- Return k.
O(log|G|) exponentiations03Order in the standard groups
| Group | Order | Maximum element order |
|---|---|---|
| Z_p* | p − 1 | p − 1, attained by generators |
| Z_n* general | φ(n) | λ(n), the Carmichael function |
| F_q* | q − 1 | q − 1; always cyclic |
| Z_n additive | n | n, attained by units |
The second row is the interesting case. For composite n the group of units need not be cyclic, so no element attains order φ(n). The largest attainable order is the Carmichael function λ(n), which divides φ(n) and is often strictly smaller — for n = 8, φ(n) = 4 while λ(n) = 2.
04Frequently asked questions
Does every element have finite order?
In a finite group, yes, by pigeonhole: the powers must eventually repeat, and the first repetition returns the identity. In infinite groups such as Z under addition, only the identity has finite order.
Why does the algorithm divide out primes one at a time?
Because the order is a divisor of |G|, so it is obtained by removing exactly those prime powers that are not needed. Testing each removal with an exponentiation confirms whether the smaller exponent still annihilates the element.
What if the group order is unknown?
Then generic methods apply, costing about the square root of the group size by baby step/giant step or Pollard's rho. Determining group order is itself a substantial problem, and for elliptic curves it requires a dedicated point-counting algorithm.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 185-190.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.