Sparse Representation for Cyclotomic Fields

Abstract

Currently, all major implementations of cyclotomic fields as well as number fields are based on a dense model in which elements are represented either as dense polynomials in the generator of the field or as coefficient vectors with respect to a fixed basis. While this representation allows for the asymptotically fastest arithmetic for general elements, it is unsuitable for fields of degree greater than 10⁴ that arise in certain applications such as character theory for finite groups. We propose instead a sparse representation for cyclotomic fields that is particularly tailored to representation theory. We implemented our ideas in magma and used it for fields of degree greater than 10⁶ over ℚ.

Keywords:

• Primary 11-04
• Secondary 11R18, 11Y16
• Cyclotomic fields
• sparse representation