The *index* and *period* of a finite monogenic semigroup $\langle x\rangle$ are the smallest numbers $i$ and $p$, respectively, satisfying $x^{i+p}=x^p$. The question is:


***Is there an algorithm to find the index/period of a finite monogenic semigroup of size $n$ in $o(n)$ (or $O(n^\epsilon)$ with $\epsilon<1$) steps?***


Note: the number $n$ is assumed to be unknown, otherwise the problem is trivial.



Finding index/period of a semigroup element
Won't Pollard's rho method give you a collision $x^k=x^\ell$ with $k>\ell$ in time roughly $O(\sqrt{n})$ (and $O(1)$ storage). From there you should be able to work back to the index and period.


