Abstract:
Groups of unknown order have been an active area of research in recent years due to their wide
variety of cryptographic applications. We focus on the most popular unknown-order group
construction: the ideal class groups of imaginary quadratic fields.
We study the two standard order computation algorithms in the literature, Shank’s babysteps-
giant-steps technique and Pollard’s rho method. Sutherland has presented a generic group
order algorithm based on the baby-steps-giant-steps approach which achieves a median complexity
of O(N0.344). An analysis of the success of this algorithm when combined with the
Pollard’s rho method is given in our thesis. In particular, we compute the precise average-case
running time of Sutherland’s Primorial steps algorithm with Pollard’s rho method, assuming
that the group order is uniformly distributed over an interval.
In the complexity computations of Sutherland’s algorithm, we are interested in the semismoothness
of group orders. We do numerical simulations with the semi-smooth probability of
class number for fundamental discriminants of the form −p and −4p with p prime. Although
class numbers (regardless of being odd or appropriately even) over the interval [1, x] have a
higher semi-smoothness probability than that for uniform integers, we provide theoretical and
experimental evidence to show that this difference in probabilities is negligible for large values
of x. Therefore, we conclude that such class groups are less vulnerable to point counting
algorithms than suggested by Sutherland.