An improved method of computing the regulator of a real quadratic function field (Q3840201)

Let \(k\) be a finite field with \(q\) elements and \(K := k(X)(\sqrt D)\) be a real quadratic field of genus \(g\). By improving algorithms contained in the first author's thesis [\textit{A. Stein}, Algorithms in real-quadratic congruence function fields (in German), Saarbrücken: Univ. des Saarlandes (1996)], the authors present an improved method for the calculation of the regulator of a real quadratic function field. The authors compare their new method with the Baby Step -- Giant Step method and show it to be superior in complexity (\(O(q^{2/5 g})\) to \(O(q^{1/2 g})\)) and in practical runtime. The main idea is, starting with an approximation of the divisor class number (obtained via the \(L\)-function), to again use Baby Step -- Giant Step to compute a multiple of the regulator. Based on the observation, that a Giant Step is much more expensive (in terms of computation time) than a Baby Step, they store only a small fraction of the Baby Step data. To be able to detect cycles within the Giant Step, they add a series of Baby Steps to each Giant Step. A side effect of this technique is the (virtual) extension of the Baby Step interval, thus allowing them to use it for a much larger range of regulators. For the entire collection see [Zbl 0891.00022].