Decision problems in quadratic function fields of high genus (Q1578426): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 02:50, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decision problems in quadratic function fields of high genus |
scientific article |
Statements
Decision problems in quadratic function fields of high genus (English)
0 references
22 October 2002
0 references
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)].
0 references
function field
0 references
complexity
0 references
class group
0 references
principal ideal test
0 references