Decision problems in quadratic function fields of high genus (Q1578426): Difference between revisions

The author gives (conditional) complexity results on a number of fundamental problems in quadratic function fields. Namely she deals with the following questions: principal ideal test, equivalence of ideals in the class group, discrete logarithms in the class group, order of ideal classes, regulator computation, (divisor) class number computation and generation of class groups. In particular, she gives complexity results (P, NP or co-NP) for all mentioned problems. For most of the results she has to use an additional assumption, namely that a small (i.e. polynomial size) generating system for the ideal class group is known. The main tool used here is the reduction theory of quadratic forms as presented e.g. in [{ it R. Scheidler}, Algorithmic number theory. ANTS-II, Lect. Notes Comput. Sci. 1122, 323-336 (1996; Zbl 0935.11049), \textit{A. Stein}, Algorithmen in reell-quadratischen Kongruenzfunktionenkörpern. Saarbrücken (1996; Zbl 0997.11511) and \textit{D. G. Cantor}, Math. Comput. 48, 95-101 (1987; Zbl 0613.14022)].