Computing Frobenius maps and factoring polynomials (Q2366168)

This paper presents a probabilistic algorithm for factoring a polynomial \(f(x)\) of degree \(n\) with one variable over a finite field. It is proved that the number of operations (addition, subtraction, multiplication, division, and zero test) is \(O((n^ 2+n\log q)(\log n)^ 2\log\log n)\), where \(q\) is the number of elements in the finite field. The authors separate the problem of factorization into three parts as the Cantor- Zassenhaus algorithm [\textit{D. G. Cantor} and \textit{H. Zassenhaus}, Math. Comput. 36, 587-592 (1981; Zbl 0493.12024)]: squarefree factorization, distinct-degree factorization, and equal-degree factorization. In dealing with the distinct-degree and equal-degree factorizations, the Frobenius map on the quotient ring \(F_ q[x]/(f)\) is used. In addition to the deterministic algorithms for distinct-degree factorization and probabilistic algorithms for equal-degree factorization presented, the authors introduce a deterministic algorithm for equal-degree factorization.