On the complexity of class group computations for large degree number fields

2018/10/26 by Gélin, Alexandre
#FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.1810.11396

Abstract

In this paper, we examine the general algorithm for class group computations, when we do not have a small defining polynomial for the number field. Based on a result of Biasse and Fieker, we simplify their algorithm, improve the complexity analysis and identify the optimal parameters to reduce the runtime. We make use of the classes \mathcal D defined in [GJ16] for classifying the fields according to the size of the extension degree and prove that they enable to describe all the number fields.

Related

• Reducing the complexity for class group computations using small defining polynomials
• An L(1/3) algorithm for ideal class group and regulator computation in certain number fields
• Class numbers of large degree nonabelian number fields
• Computational class field theory
• New techniques for computing the ideal class group and a system of fundamental units in number fields