6
$\begingroup$

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?

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .