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

Quadratic extensions (11R11) Units and factorization (11R27) Arithmetic theory of algebraic function fields (11R58) Algebraic number theory computations (11Y40)

Review text

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].

Recommendations

Cited in

(5)

This page was built for publication: An improved method of computing the regulator of a real quadratic function field

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3840201)