Abstract : Computing the class group and the unit group of a number field is a famous problem of algorithmic number theory. This has also applications in ryptography, for instance in class group based cryptography, or for the cryptanalysis of algebraic lattice problems.
Subexponential time algorithms are known to solve this problem in any number fields, but they heavily rely on heuristics. The only non-heuristic (but still under ERH) known algorithm, due to Hafner and McCurley, is restricted to imaginary quadratic number fields. In this talk, I will present a rigorous subexponential time algorithm computing units and class group (and more generally S-units) in any number field, assuming the extended Riemann hypothesis (ERH).
This is a joint work with Koen de Boer and Benjamin Wesolowski.