Jeudi 8 mars 2018 à 16h00 en salle C48

Anand Kumar Naranayan (UPMC)

Titre : Drinfeld Modules, Hasse Invariants and Factoring Polynomials over Finite Fields

Résumé :

We outline three novel algorithms to factor polynomials over finite
fields using the arithmetic of Drinfeld modules. The first algorithm
estimates the degree of an irreducible factor of a polynomial from
Euler-Poincare characteristics of random Drinfeld modules. Knowledge
of a factor degree allows one to rapidly extract all factors of that
degree. The second algorithm is a random Drinfeld module analogue of
Berlekamp's algorithm, partly inspired by Lenstra's elliptic curve
method for integer factorization. The third algorithm employs Drinfeld
modules with complex multiplication. The main idea is to compute a
lift of the Hasse invariant with Deligne's congruence playing a
critical role. We will discuss practical implementations and
complexity theoretic implications of the algorithms.
The talk will be based on the papers
https://arxiv.org/abs/1712.00669
https://arxiv.org/abs/1504.07697