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)

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