Deterministic analysis of aleatoric methods of polynomial factorization over finite fields (Q1323866)

This paper deals with the problem of factoring a monic polynomial \(f\) over a finite field \(GF(q)\) into a product of irreducible monic polynomials over \(GF(q)\). By either the method of \textit{E. R. Berlekamp} [Factoring polynomials over large finite fields, Math. Comput. 24 (1970), 713-735 (1971; Zbl 0247.12014)] or the method of \textit{D. G. Cantor} and \textit{H. Zassenhaus} [Math. Comput. 36, 587-592 (1981; Zbl 0493.12024)] this problem is reduced to the problem of finding the roots of a polynomial for which it is known that the polynomial is a product of distinct linear factors over \(GF(q)\). Thus without loss of generality it may be assumed that \(f= \prod_{i=1}^ n (t-\xi_ i)\), where \(\xi_ 1, \xi_ 2, \dots, \xi_ n\) are distinct nonzero elements of \(GF(q)\). The methods of Berlekamp and Cantor-Zassenhaus are both probabilistic methods. In the paper under review the authors propose a deterministic version of the Cantor-Zassenhaus algorithm. It is conjectured that this algorithm has complexity \(O(n^ 4 \log p)\), where \(n= \text{degree} (f)\) and \(p\) is the characteristic of \(GF(q)\). A combinatorial problem is formulated whose solution would imply the truth of this conjecture. The authors also present a new deterministic factorization algorithm that requires knowledge of a primitive root of \(GF(q)\).