The parallelized Pollard kangaroo method in real quadratic function fields (Q2781226)

The Pollard kangaroo method [\textit{J. Pollard}, Math. Comput. 32, 918-924 (1978; Zbl 0382.10001)], also called the lambda method, is a space-efficient algorithm for computing discrete logarithms in finite abelian groups. Recently, parallelized versions of this method have been proposed [\textit{P. C. van Oorschot} and \textit{M. J. Wiener}, J. Cryptology 12, 1-28 (1999; Zbl 0992.94028) and \textit{J. M. Pollard}, J. Cryptology 13, 437-447 (2000; Zbl 0979.11057)]. NEWLINENEWLINENEWLINEThis paper begins with an exposition of these two parallelized versions, including an experimental comparison of their efficiency in computing elliptic discrete logarithms in practice. Then it turns to its main subject, which is the adaptation of the parallelized kangaroo method to the quick computation of class numbers and regulators of ``real quadratic function fields,'' i.e., quadratic extensions of the rational function field over a finite field, in which the place at infinity splits. In particular, the authors set a new record by computing a 29-digit class number and regulator of a genus-3 real quadratic function field.