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-31
  10:00
  Salle 2
  Wessel 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-07
  10:00
  Salle 2
  Andrea 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-14
  10:00
  Salle 2
  Maxime Plançon (IBM Zürich)
  TBA
• 2023-02-21
  10:00
  Salle 2
  Floris Vermeulen (KU Leuven)
  TBA
• 2023-03-07
  10:00
  Salle 2
  Ross Paterson (University of Bristol)
  TBA
• 2023-03-14
  10:00
  Salle 2
  Leonardo Colô (Université Aix-Marseille)
  TBA
• 2023-03-21
  10:00
  Salle 2
  Mathieu Dutour (University of Alberta, USA)
  TBA