Reducing the complexity for class group computations using small defining polynomials

2018/10/29 by Alexandre Gélin, Gélin, Alexandre
Computer Science · #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Symbolic Computation (cs.SC)

paper · pdf · doi:10.48550/arxiv.1810.12010

openalex publication_date 2018/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we describe an algorithm that efficiently collect relations in class groups of number fields defined by a small defining polynomial. This conditional improvement consists in testing directly the smoothness of principal ideals generated by small algebraic integers. This strategy leads to an algorithm for computing the class group whose complexity is possibly as low as L_|Δ_{\mathbf K}|((1)/(3)).

Related

• On the complexity of class group computations for large degree number fields
• An L(1/3) algorithm for ideal class group and regulator computation in certain number fields
• The complexity of class polynomial computation via floating point approximations
• New techniques for computing the ideal class group and a system of fundamental units in number fields
• An improvement to an algorithm of Belabas, Diaz y Diaz and Friedman