IMB > Recherche > Séminaires

Séminaire de Théorie Algorithmique des Nombres

Responsables : Razvan Barbulescu et Wessel Van Woerden

Page du séminaire

  • Le 5 mars 2024 à 11:00
  • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Yuri Bilu IMB
    Skolem meets Schanuel
    A linear recurrence of order~$r$ over a number field~$K$ is a map ${U:\mathbb{Z}\to K}$ satisfying a relation of the form
    $$
    U(n+r)=a_{r-1}U(n1)+ \cdots+ a_0U(n) \qquad (n\in \mathbb{Z}),
    $$
    where ${a_0, \ldots, a_{r-1}\in K}$ and ${a_0e 0}$. A linear recurrence is called simple if the characteristic polynomial ${X^r-a_{r-1}X^{r-1}-\ldots- a_0}$ has only simple roots, and non-degenerate if ${\lambda/\lambda'}$ is not a root of unity for any two distinct roots $\lambda, \lambda'$ of the characteristic polynomial. The classical Theorem of Skolem-Mahler-Lech asserts that a non-degenerate linear recurrence may have at most finitely many zeros. However, all known proofs of this theorem are non-effective and do not produce any tool to determine the zeros.


    In this talk I will describe a simple algorithm that, when terminates, produces the rigorously certified list of zeros of a given simple linear recurrence. This algorithm always terminates subject to two celebrated conjectures: the $p$-adic Schanuel Conjecture, and the Exponential Local-Global Principle. We do not give any running time bound (even conditional to some conjectures), but the algorithm performs well in practice, and was implemented in the \textit{Skolem tool}
    $$
    \text{https://skolem.mpi-sws.org/}
    $$
    that I will demonstrate. This is a joint work with Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser and James Worrell.
  • Le 12 mars 2024 à 11:00
  • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Olivier Ruatta Université de Limoges
    Polynômes linéarisés et cryptographie en métrique rang

  • Le 19 mars 2024 à 11:00
  • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Rocco Mora CISPA
    TBA

  • Le 26 mars 2024 à 11:00
  • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Bastien Pacifico LIRMM
    From Chudnovsky-type algorithms to locally recoverable codes
    Chudnovsky's method makes it possible to construct multiplication algorithms in finite fields with good bilinear complexity, i.e. a small number of bilinear multiplications in the base field. However, their total complexity and the difficulty of efficiently constructing these algorithms are unfavorable.

    Historically, these are evaluation/interpolation algorithms using rational points of algebraic curves/rational places of function fields. Using asymptotically optimal towers, the existence of algorithms with bilinear complexity that is linear in the degree of extension has been proven. But these algorithms are not constructible in polynomial time.
    Another approach is a recursive construction using places of increasing degrees. It provides algorithms with a quasi-linear bilinear complexity, but constructible in polynomial time.

    We will introduce a hybrid construction, taking the best of both strategies to obtain algorithms with linear bilinear complexity that can be constructed in polynomial time.

    Secondly, we will see that some locally recoverable codes, where the recovery of a corrupted symbol is possible using a small amount of other symbols, appear naturally in the recursive construction of Chudnovsky-type algorithms. We will define and study these codes.
  • Le 7 mai 2024 à 11:00
  • Séminaire de Théorie Algorithmique des Nombres
    salle 2
    Félix Huber Labri
    TBA

    Afficher 2022 - 2021 - 2020 - 2019 - 2018 - 2017 - 2016 - 2015 - antérieurs