Factoring Polynomials over Finite Fields using Drinfeld Modules with Complex Multiplication
share
We present novel algorithms to factor polynomials over a finite field _q of odd characteristic using rank 2 Drinfeld modules with complex multiplication. The main idea is to compute a lift of the Hasse invariant (modulo the polynomial f(x) ∈_q[x] to be factored) with respect to a Drinfeld module ϕ with complex multiplication. Factors of f(x) supported on prime ideals with supersingular reduction at ϕ have vanishing Hasse invariant and can be separated from the rest. A Drinfeld module analogue of Deligne's congruence plays a key role in computing the Hasse invariant lift. We present two algorithms based on this idea. The first algorithm chooses Drinfeld modules with complex multiplication at random and has a quadratic expected run time. The second is a deterministic algorithm with O(√(p)) run time dependence on the characteristic p of _q.
READ FULL TEXT