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?

  • $\begingroup$ 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 :-) $\endgroup$ Sep 29 '14 at 20:57
  • $\begingroup$ 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. $\endgroup$ Sep 29 '14 at 20:58
  • $\begingroup$ @JyrkiLahtonen Well, it is still interesting if it is possible. $\endgroup$
    – khajvah
    Sep 29 '14 at 21:00
  • 1
    $\begingroup$ See also en.m.wikipedia.org/wiki/Cycle_detection. $\endgroup$
    – lhf
    Sep 29 '14 at 21:19
  • 1
    $\begingroup$ And Sutherland's 2007 Phd thesis: Order computations in generic groups. $\endgroup$
    – ccorn
    Sep 29 '14 at 21:21

This is a good question. As you may have gathered from the comments, in the absence of any further information about the group, the answer is no, all you can do is to successively try higher powers.

But in most situations that arise in practice you do have extra information of one kind or another. For example, if your element is a matrix over a finite field, or even over the rational number or a number field, then the set of all possible orders of elements is known (at least in theory).

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}}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.