Square root-based black-box group algorithm for element order-finding problem

Summary

Item	Value
Problem being solved	element order-finding problem in a group with a known upper bound on its order
Input format	group $G$ specified via an encoding, upper bound $B$ on the order of $G$. Codeword for an element $g$ of $G$.
Output format	positive integer that equals the order of $g$
Running time	Roughly $O(N\operatorname {polylog} N)$ plus $O({\sqrt {B}})$ times the time taken for group multiplication. In particular, the number of times that we need to do the group multiplication is $O(\min\{{\sqrt {B}},r\})$ (where $r$ is the order of the element), which could be smaller than $O(N)$. In fact, if $B=O(N)$, then the group multiplications need to be performed only $O(\min\{{\sqrt {N}},r\})$ times. If we use a multi-encoding instead of an encoding, then we also need to do, in the extreme case, about $O(N)$ equality tests.
Competing algorithms	brute-force black-box group algorithm for element order-finding problem: does $O(N)$ group multiplications. order factorization-based black-box group algorithm for element order-finding problem: helpful if the order of the group is known and its factorization is known. In this case, we can make a list of all divisors of the order and compute only those powers using the repeated squaring algorithm for power computation problem. If $N$ has few prime factors, this can take a lot less time.
Parallelizable version	Tricky to implement, because we want the smallest that works. We can use parallelization somewhat along with on-the-fly reallocation of resources.

Idea and outline

The algorithm as presented here relies only on the multiplication algorithm and knowledge of the identity element, and it does not require the use of the inverse map.

Let $m$ be a positive integer chosen such that $m-1$ is greater than ${\sqrt {B}}$.

Consider two sets:

$S_{1}$ is the set of powers $\{g,g^{2},\dots ,g^{m-1}\}$

$S_{2}$ is the set of similar powers for $g^{m}$, i.e., $\{g^{m},(g^{m})^{2},\dots ,(g^{m})^{m-1}\}$.

The algorithm is as follows:

1. We construct $S_{1}$ left to right, with each new element obtained by multiplying its predecessor by $g$. If at any stage we get to the identity element, we stop there -- that's the order of $g$. If not, we constructed the whole of $S_{1}$.
2. $g^{m}$ is constructed by multiplying the last element of $S_{1}$ by $g$. We then construct the elements of $S_{2}$ from left to right, with each new element obtained by multiplying its predecessor by $g^{m}$. Every time we construct a new element of $S_{2}$, we check if it is equal to any of the elements of $S_{1}$, going from right to left on $S_{1}$. Suppose the first collision happens for $(g^{m})^{a}=g^{b}$. Then, the order of $g$ is $ma-b$.