Mon, 13 Jun 2022 13:00 Rigorous computation of class group and unit group by Alice Pellet-Mary (CNRS, Université de Bordeaux)

Computing the class group and the unit group of a number field is an important problem of algorithmic number theory. Recently, it has also become an important problem in cryptography, since it is used in multiple algorithms solving the shortest vector problem in ideal lattices.

Subexponential algorithms (in the discriminant of the number field) are known to solve this problem in any number fields, but they heavily rely on heuristics. The only non-heuristic known algorithm, due to Hafner and McCurley, is restricted to imaginary quadratic number fields.

In this talk, I will present a rigorous subexponential algorithm computing units and class group (and more generally T-units) in any number field, assuming the extended Riemann hypothesis.

This is a joint work with Koen de Boer and Benjamin Wesolowski.

Speaker Bio:

Alice is a CNRS researcher (chargée de recherche) at the university of Bordeaux. She is part of the Institut de Mathématiques de Bordeaux (IMB) and of the Lfant inria team. She is interested in lattice based cryptography, and more specifically in the hardness of algorithmic problems related to algebraically structured lattices.

Venue: Online