logo IMB
Retour

Séminaire de Théorie Algorithmique des Nombres

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

Jean-François Biasse

( University of South Florida )

Salle 385

le 05 juillet 2018 à 10:00

Let L=Q(a^ˆsˇd1,...,a^ˆsˇdn)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(a^ˆ†),Size(S))eA~(a^ˆsˇlnd)Poly(log(∆),Size(S)) e^{Õ(√ln d)} where d=maxia^‰¤ndid=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 OLO_L of L in time Poly(log(a^ˆ†))eA~(a^ˆsˇlogd)Poly(log(∆)) e^{Õ(√log d)}. When log(d)a^‰¤log(log(a^ˆ†))clog(d)≤log(log(∆))^c for some constant c<2c < 2, these methods run in polynomial time. We implemented our algorithm using Sage 7.5.1.