Decision problems in quadratic function fields of high genus
type: Item
instance of: scholarly article
title: Decision problems in quadratic function fields of high genus
zbMATH Open document ID: 0999.11075
published in: Journal of Complexity
publication date: 2002-10-22T00:00:00Z
review text: 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)].
reviewed by: Claus Fieker
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11R11
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11R58
zbMATH DE Number: 1496870
zbMATH Keywords: function field
zbMATH Keywords: complexity
zbMATH Keywords: class group
zbMATH Keywords: principal ideal test
author: Renate Scheidler
MaRDI profile type: Publication
OpenAlex ID: W2095449392
cites work: Q4847910
cites work: Q4375592
cites work: Explicit Bounds for Primality Testing and Related Problems
cites work: Q3478481
cites work: Some remarks concerning the complexity of computing class groups of quadratic fields
cites work: Computing in the Jacobian of a Hyperelliptic Curve
cites work: Q4143385
cites work: A Rigorous Subexponential Algorithm For Computation of Class Groups
cites work: Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
cites work: Computing discrete logarithms in real quadratic congruence function fields of large genus
cites work: Q3840199
cites work: Q4375623
cites work: Key-exchange in real quadratic congruence function fields
cites work: Q4380338
cites work: Some Methods for Evaluating the Regulator of a Real Quadratic Function Field
cites work: Algebraic function fields and codes
DOI: 10.1006/JCOM.2000.0542
description: scientific article; zbMATH DE number 1496870