Anand Narayanan

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.