Polynomial factorization over finite fields by computing Euler-Poincaré characteristics of Drinfeld modules

The second algorithm is a random Drinfeld module analogue of Berlekamp's algorithm. During the course of its analysis, we prove a new bound on degree distributions in factorization patterns of polynomials over finite fields in certain short intervals.