# Ways to find the order of an element in a group

Is there a better way of finding the order of an element in a group other than circling until the identity is reached?

Is there or CAN there be a better general ways of finding orders of elements? (if no, please, explain why there can't be any ways)

An example I have is a multiplicative group of elements $Z_{20}$ under modulo 20. Do I have to circle over every element to find orders?

• For multiplicative groups of residue classes there is the Carmichael function with the property that the order is a factor of the value of the Carmichael function. An extended version of Lagrange's theorem. But, really, $|\Bbb{Z}_{20}^*|$ has eight elements, so it takes a few seconds with pen-and-pencil to cycle through the powers. If the possible order would be a 30-digit number, then you would have a reason to complain :-) Sep 29 '14 at 20:57
• In general for finite abelian groups their structure theory gives helpful information. But it is a bit difficult to gauge what kind of information you are looking for. Sep 29 '14 at 20:58
• @JyrkiLahtonen Well, it is still interesting if it is possible. Sep 29 '14 at 21:00
• – lhf
Sep 29 '14 at 21:19
• Sep 29 '14 at 21:21

In such situations, you typically have a multiplicative upper bound for the order. In other words, you know a (possibly very large) integer $N$ such that the order of the element $g$ divides $N$. Then you can proceed as follows
For all primes $p$ dividing $N$, compute $g^{N/p}$. If $g^{N/p} = 1$ for some $p$, then replace $N$ by $N/p$ and start again - note that there will be a maximum of $\log n$ reductions of this kind. Otherwise, if $g^{N/p} \ne 1$ for all $p$, then the order of $g$ must be $N$.
Note also that computing $g^N$ can be accomplished on $O(\log n)$ group operations, by writing $N$ in binary $N = 2^{n_1} + \cdots + 2^{n_k}$, and then you can compute $g^N$ as $g^{2^{n_1}} \cdots g^{2^{n_k}}$.