Thirteenth Algorithmic Number Theory Symposium ANTS-XIII University of Wisconsin, Madison July 16 – 20, 2018 Thirteenth Algorithmic Number Theory Symposium (ANTS-XIII) July 16 – 20, 2018

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

Jean-François Biasse and Christine van Vredendaal

Abstract: Let L=Q(√d₁, . . . ,√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≤nd_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.

Published Paper
Talk Slides (PowerPoint)