Decision problems in quadratic function fields of high genus

DOI10.1006/JCOM.2000.0542MaRDI QIDQ1578426zbMATH OpenOpenAlexFDO

Authors Renate Scheidler

Publication date 22 October 2002

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/48bc046d79504328b0b2537ea41db90a774f7fd8

zbMATH Keywords

class groupcomplexityfunction fieldprincipal ideal test

Mathematics Subject Classification ID

Quadratic extensions (11R11) Arithmetic theory of algebraic function fields (11R58) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25)

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

Recommendations

• Some remarks concerning the complexity of computing class groups of quadratic fields
• scientific article; zbMATH DE number 733559
• scientific article; zbMATH DE number 6488046

Cites work

• A Rigorous Subexponential Algorithm For Computation of Class Groups
• Algebraic function fields and codes
• Computing discrete logarithms in real quadratic congruence function fields of large genus
• Computing in the Jacobian of a Hyperelliptic Curve
• Explicit Bounds for Primality Testing and Related Problems
• scientific article; zbMATH DE number 4148210 (Why is no real title available?)
• scientific article; zbMATH DE number 1186974 (Why is no real title available?)
• scientific article; zbMATH DE number 3572260 (Why is no real title available?)
• scientific article; zbMATH DE number 1113820 (Why is no real title available?)
• scientific article; zbMATH DE number 1113849 (Why is no real title available?)
• scientific article; zbMATH DE number 1128465 (Why is no real title available?)
• scientific article; zbMATH DE number 799760 (Why is no real title available?)
• Key-exchange in real quadratic congruence function fields
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Some Methods for Evaluating the Regulator of a Real Quadratic Function Field
• Some remarks concerning the complexity of computing class groups of quadratic fields

Cited in

(5)

• Some remarks concerning the complexity of computing class groups of quadratic fields
• An algorithm for the principal ideal problem in indefinite quaternion algebras
• scientific article; zbMATH DE number 733559 (Why is no real title available?)
• scientific article; zbMATH DE number 1113849 (Why is no real title available?)
• Solving norm equations in global function fields

This page was built for publication: Decision problems in quadratic function fields of high genus

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