Factoring polynomials over finite fields: A survey (Q5928877)

The paper surveys several algorithms for the factorization of univariate polynomials over finite fields, emphasizing the main ideas of the methods. The problem addressed is: Given a monic univariate polynomial \(f\in F_q [x]\), find the complete factorization \(f = f_1^{e_1} f_2^{e_2}\cdots f_k^{e_k}\) where \(f_1,\dots,f_k\) are pairwise distinct monic irreducible polynomials and \(e_1,\dots,e_k\) are positive integers. The complexity of the algorithms discussed are given in terms of the number of operations in \({F}_q\) and the ``soft'' \(O\) notation is used that ignores logarithmic factors. Some discussion is given of the practicality of fast arithmetic and matrix arithmetic. Many general factoring algorithms comprise the following three steps: SFF: square free factorization that reduces the given polynomial to one which contains all the irreducible factors to degree one. DDF: distinct degree factorization splits the squarefree polynomial into a product of polynomials whose irreducible factors all have the same degree.