100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Thierry Gallay

Anand Narayanan

Drinfeld modules, Hasse invariants and factoring polynomials over finite fields.
Jeudi, 20 Février, 2020 - 10:30
Résumé : 

We outline three novel algorithms to factor polynomials in one variable 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. The second algorithm is a variant of the Pantchichkine-Potemine algorithm, a random Drinfeld module amalgam of Berlekamp's algorithm/Lenstra's elliptic curve method for integer factorization. The third algorithm employs Drinfeld modules with complex multiplication and will be the primary focus of the talk. 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.

Institution de l'orateur : 
Sorbonne Université
Thème de recherche : 
Théorie des nombres
Salle : 
4
logo uga logo cnrs