Vol. 2, 2019

 Recent Volumes 2: ANTS XIII 1: ANTS X
 The Open Book Series About the Series Ethics Statement Other MSP Publications
Fast multiquadratic $S$-unit computation and application to the calculation of class groups

Jean-François Biasse and Christine Van Vredendaal

Vol. 2 (2019), No. 1, 103–118
Abstract

Let $L=ℚ\left(\sqrt{{d}_{1}},\dots ,\sqrt{{d}_{n}}\right)$ be a real multiquadratic field and $S$ be a set of prime ideals of $L$. 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\left(log\left(\Delta \right),Size\left(S\right)\right){e}^{\stackrel{˜}{O}\left(\sqrt{lnd}\right)}$ where $d={\prod }_{i\le n}{d}_{i}$ and $\Delta$ is the discriminant of $L$. We use this method to compute the ideal class group of the maximal order ${\mathsc{O}}_{L}$ of $L$ in time $Poly\left(log\left(\Delta \right)\right){e}^{\stackrel{˜}{O}\left(\sqrt{logd}\right)}$. When $log\left(d\right)\le log{\left(log\left(\Delta \right)\right)}^{c}$ for some constant $c<2$, these methods run in polynomial time. We implemented our algorithm using Sage 7.5.1.

Keywords
ideal class group, $S$-unit group, multiquadratic fields
Mathematical Subject Classification 2010
Primary: 11R04, 11R29, 11R65, 11Y99
Secondary: 11R11, 11R16, 11S20, 11Y50