Current
The seminar is held on Tuesdays from 10 to 11 and is organized by Razvan Barbulescu and Wessel van Woerden. When on site, it takes place in room 2 of IMB. To get announcements, you can subscribe to the lfant-seminar mailing list.- 2023-01-3110:00Salle 2Wessel van Woerden (IMB)An Algorithmic Reduction Theory for Binary Codes, LLL and more
We will discuss an adaptation of the algorithmic reduction theory of lattices to binary codes. This includes the celebrated LLL algorithm (Lenstra, Lenstra, Lovasz, 1982), as well as adaptations of associated algorithms such as the Nearest Plane Algorithm of Babai (1986). Interestingly, the adaptation of LLL to binary codes can be interpreted as an algorithmic version of the bound of Griesmer (1960) on the minimal distance of a code.
- 2023-02-0710:00Salle 2Andrea Lesavourey (Irisa)Calcul de racines de polynômes dans un corps de nombres
Computing roots of elements is an important step when solving various tasks in computational number theory. It arises for example during the final step of the General Number Field Sieve~(Lenstra et al. 1993). This problem also intervenes during saturation processes while computing the class group or $S$-units of a number field (Biasse and Fieker).
It is known from the seminal paper introducing the LLL algorithm that one can recover elements of a given number field $K$ given approximations of one of their complex embeddings. This can be used to compute roots of polynomials. In the first part of this presentation, I will describe an extension of this approach that take advantage of a potential subfield $k$, which replace the decoding of one element of $K$ by the decoding $[K:k]$ elements of $k$, to the cost of search in a set of cardinality $d^{[K:k]}$ where $d$ is the degree of the targetted polynomial equation. We will also describe heuristic observations that are useful to speed-up computations.
In the second part of the presentation, we will describe methods to compute $e$-th roots specifically. When $K$ and $e$ are such that there are infinitely many prime integers $p$ such that $\forall \mathfrak{p} \mid p, p^{f(\mathfrak{p}\mid p)}\not\equiv1\bmod e$, we reconstruct $x$ from $ x \pmod {p_1}, \dots, x \pmod {p_r} $ using a generalisation of Thomé’s work on square-roots in the context of the NFS~(Thomé). When this good condition on $K$ and $n$ is not satisfied, one can adapt Couveignes’ approach for square roots~(Couveignes) to relative extensions of number fields $K/k$ provided $[K:k]$ is coprime to $e$ and infinitely many prime integers $p$ are such that each prime ideal $\mathfrak{p}$ of $\mathcal{O}_k$ above $p$ is inert in $K$. - 2023-02-1410:00Salle 2Maxime Plançon (IBM Zürich)TBA
- 2023-02-2110:00Salle 2Floris Vermeulen (KU Leuven)TBA
- 2023-03-0710:00Salle 2Ross Paterson (University of Bristol)TBA
- 2023-03-1410:00Salle 2Leonardo Colô (Université Aix-Marseille)TBA
- 2023-03-2110:00Salle 2Mathieu Dutour (University of Alberta, USA)TBA