Integer factoring algorithms have traditionally been compared by focusing on the worst-case running time. {\it J. Hafner} and {\it K. McCurley} [J. Algorithms 10, 531-556 (1989; Zbl 0689.68055)] approached the comparison of different algorithms by studying (roughly speaking) the number of integers less than $x$ which can be factored in time less than $t$. They compared the trivial trial division method with Lenstra’s elliptic curve method, showing that the latter can factor many more integers. In the paper under review, the authors add two more factoring methods to the list of algorithms studied in this way: Pollard’s $p-1$ and Williams’ $p+ 1$ methods. They find that these two algorithms perform, in this average sense, somewhere strictly between the trial division and the elliptic curve method (as expected).
Reviewer: J.L.Hafner (San José)