A modification of Shanks’ baby-step giant-step algorithm

Abstract:

I describe a modification to Shanks’ baby-step giant-step algorithm for computing the order $n$ of an element $g$ of a group $G$, assuming $n$ is finite. My method has the advantage of being able to compute $n$ quickly, which Shanks’ method fails to do when the order of $G$ is infinite, unknown, or much larger than $n$. I describe the algorithm in detail. I also present the results of implementations of my algorithm, as well as those of a similar algorithm developed by Buchmann, Jacobson, and Teske, for calculating the order of various ideal classes of imaginary quadratic orders.