Fast multiquadratic S-unit computation and application to the calculation of class groups

Let $L=Q(√d_1, ... ,√d_n)$ be a real multiquadratic field and S be a set of prime ideals of L that does not contain any divisors of 2. In this paper, we present a heuristic algorithm for the computation of the S-class group and the S-unit group that runs in time $Poly(log(∆),Size(S)) e^{Õ(√ln d)}$ where $d=max_{i≤n} d_i$ and ∆ is the discriminant of L. We use this method to compute the ideal class group of the maximal order $O_L$ of L in time $Poly(log(∆)) e^{Õ(√log d)}$. When $log(d)≤log(log(∆))^c$ for some constant $c < 2$, these methods run in polynomial time. We implemented our algorithm using Sage 7.5.1.