Some remarks concerning the complexity of computing class groups of quadratic fields

DOI10.1016/0885-064X(91)90039-ZMaRDI QIDQ1179460zbMATH OpenFDO

Authors Johannes Buchmann, Hugh C. Williams

Publication date 26 June 1992

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

Full work available at URL https://doi.org/10.1016/0885-064X(91)90039-Z

zbMATH Keywords

class group computationscomplexityquadratic number fields

Mathematics Subject Classification ID

Quadratic extensions (11R11) Class numbers, class groups, discriminants (11R29) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25)

Review text

The authors obtain several results concerning the complexity of computations in quadratic number fields \(F\). Under the assumption of the generalized Riemann hypothesis they prove among other things that the following problems are in \(NP\cap \hbox{co-}NP\) for every order \(\mathcal O\) of \(F\): (i) Is a given ideal \(A\) of \(\mathcal O\) principal? (ii) Do given ideals \(A_ 1,\dots,A_ k\) of \(\mathcal O\) generate the class group?

Recommendations

• Decision problems in quadratic function fields of high genus
• scientific article; zbMATH DE number 799782
• scientific article; zbMATH DE number 4137898

Cites work

• 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 4171062 (Why is no real title available?)
• scientific article; zbMATH DE number 3572260 (Why is no real title available?)
• On the Parallel Generation of the Residues for the Continued Fraction Factoring Algorithm

Cited in

(9)

• Decision problems in quadratic function fields of high genus
• Short proofs using compact representations of algebraic integers
• scientific article; zbMATH DE number 4173143 (Why is no real title available?)
• scientific article; zbMATH DE number 4137898 (Why is no real title available?)
• scientific article; zbMATH DE number 1303169 (Why is no real title available?)
• scientific article; zbMATH DE number 784878 (Why is no real title available?)
• scientific article; zbMATH DE number 799782 (Why is no real title available?)
• On the Computation of Unit Groups and Class Groups of Totally Complex Quartic Fields
• Fast multiquadratic S-unit computation and application to the calculation of class groups

This page was built for publication: Some remarks concerning the complexity of computing class groups of quadratic fields

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