A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented. To factor a polynomial of degree n over Fq, the number of arithmetic operations in Fq is O((n2+nlog q). (log n)2 loglog n). 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.
- Subject classifications: 68Q40, 11Y16, 12Y05
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics
- Computational Mathematics