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