A proof of the conjectured run time of the Hafner-McCurley class group algorithm

DOI10.3934/AMC.2021055OpenAlexW3216280874MaRDI QIDQ6047436

Muhammed Rashad Erukulangara, Jean-François Biasse

Publication date: 12 September 2023

Published in: Advances in Mathematics of Communications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3934/amc.2021055

zbMATH Keywords

imaginary quadratic fieldsideal class groupsindex calculusgroups of unknown order

Mathematics Subject Classification ID

Quadratic extensions (11R11) Number-theoretic algorithms; complexity (11Y16) Group rings of finite groups and their modules (group-theoretic aspects) (20C05) Algebraic number theory computations (11Y40) Class numbers, class groups, discriminants (11R29) General binary quadratic forms (11E16)

Related Items (1)

An algorithm for solving the principal ideal problem with subfields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improvements in the computation of ideal class groups of imaginary quadratic number fields
• Expander graphs based on GRH with an application to elliptic curve cryptography
• A key-exchange system based on imaginary quadratic fields
• Subexponential algorithms for class group and unit computations
• CSI-FiSh: efficient isogeny based signatures through class group computations
• The shifted number system for fast linear algebra on integer matrices
• Subexponential time relations in the class group of large degree number fields
• Quadratic sieving
• Subexponential class group and unit group computation in large degree number fields
• Fast heuristic algorithms for computing relations in the class group of a quadratic order, with applications to isogeny evaluation
• Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model
• Explicit Bounds for Primality Testing and Related Problems
• A Rigorous Subexponential Algorithm For Computation of Class Groups
• A Probabilistic Factorization Algorithm with Quadratic Forms of Negative Discriminant
• Applying sieving to the computation of quadratic class groups
• Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
• Practical Improvements to Class Group and Regulator Computation of Real Quadratic Fields
• A reverse Minkowski theorem
• Simple verifiable delay functions
• A Las Vegas algorithm for computing the smith form of a nonsingular integer matrix
• An 𝐿(1/3) algorithm for ideal class group and regulator computation in certain number fields
• Short Generators Without Quantum Computers: The Case of Multiquadratics
• Computing Generator in Cyclotomic Integer Rings
• Efficient verifiable delay functions
• Fast multiquadratic S-unit computation and application to the calculation of class groups
• Norm relations and computational problems in number fields

This page was built for publication: A proof of the conjectured run time of the Hafner-McCurley class group algorithm