An algorithm to compute relative cubic fields

Let k be an imaginary quadratic number field (with class number 1). We describe a new, essentially linear-time algorithm, to list all isomorphism classes of cubic extensions L/k up to a bound X on the norm of the relative discriminant ideal. The main tools are Taniguchi's generalization of Davenport-Heilbronn parametrisation of cubic extensions, and reduction theory for binary cubic forms over imaginary quadratic fields. Finally, we give numerical data for k=Q(i), and we compare our results with ray class field algorithm ones, and with asymptotic heuristics, based on a generalization of Roberts' conjecture.