Element order-finding problem

Definition

The element order-finding problem refers to a general class of problems where a group is specified by means of a group description rule (such as an encoding of a group or a multi-encoding of a group), an element of the group is specified, and we need to determine the order of the element, i.e., the order of the cyclic subgroup generated by that element.

Solution

Using an encoding or multi-encoding

Algorithm	Idea	What does it rely on?
brute-force black-box group algorithm for element order-finding problem	The idea is to keep computing positive powers of the element until we hit the identity element.	the multiplication algorithm, being able to identify the identity element.
square root-based black-box group algorithm for element order-finding problem	It improves over the brute-force algorithm in reducing the number of group multiplications that need to be done. The idea is to take a number $m$ that is greater than the square root of the order of the group. Compute the first $m-1$ powers of the element and the first $m$ powers of its $m^{th}$ power. Now, check for collisions between these computed values.	A suitable upper bound on the order. The algorithm is useful for encodings and for multi-encodings where equality testing is considerably faster than the group operations.
order factorization-based black-box group algorithm for element order-finding problem	Compute only those powers that correspond to factors of the order of the group. Use repeated powering to save time on these computations.	Known factorization of the order of the group. It is most useful when the order of the group has very few prime factors. The algorithm proceeds even faster when there exist faster algorithms for the power computation problem than the naive repeated squaring algorithm for power computation.