Index-Calculus Algorithms for Computing Class Groups of Quartic Number Fields
Date
2024-09-17
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We address the problem of quickly computing the class group and unit group for quartic number fields of large discriminant. Index-calculus algorithms are the fastest way to solve this problem for arbitrary number fields. Our focus is primarily on improvements to relation generation, one of the main stages in an index-calculus algorithm. In the quadratic case, the self-initialization approach to relation generation developed by Jacobson has been very successful, but applying this idea to quartic fields has not been attempted. We present a novel generalization of this approach that is applicable to quartic number fields. Additionally, we characterize the efficiency of our method in terms of the size of the roots of the field’s defining polynomial. We discuss our implementation of a complete index-calculus algorithm using this approach. Our implementation's relation generation produces relations significantly faster than the current state-of-the-art, Magma. Our implementation of the complete algorithm, including the improved relation generation, is faster than Magma for number fields whose defining polynomial has small roots, and is comparable for typical number fields.
Description
Keywords
computation, algorithm, number theory, algebraic number theory, class group, number field, index-calculus, performance
Citation
Marquis, D. (2024). Index-calculus algorithms for computing class groups of quartic number fields (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.