Computing Class Groups of Cubic Orders Using Kleinjung’s Sieving Method

Abstract

We introduce two techniques to generate relations in the computation of class groups of orders of number fields using Buchmann’s index calculus method. In particular, we focus on primitive cubic orders. The first is an adaptation of the homogeneous method from the number field sieve to compute the class groups of a special class of orders known as rationally monogenic orders, which includes primitive cubic orders. The second is a generalisation of recent work by Kleinjung on the quadratic sieve to arbitrarily high degrees. We combine the two into one algorithm, implemented it, and test its performance against MAGMA. The results indicate that our method outperforms MAGMA if the given defining form is skew, and essentially tying MAGMA if the given form is flat.