Computing Frobenius maps and factoring polynomials
Joachim von zur Gathen, Victor Shoup · 1992
A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented whose asymptotic running time improves upon previous results. To factor a polynomial of degree n over Fq, the algorithm uses O((n2 + n log q)•(log n)2 log log n) arithmetic operations in Fq. The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.