A generalisation of the Cantor-Zassenhaus algorithm (Q1377270)

This paper is concerned with the computational problem of factoring a univariate polynomial \(f\) over a finite field \(F_q\). Many such algorithms already exist, such as the Cantor-Zassenhaus algorithm [\textit{D. G. Cantor} and \textit{H. Zassenhaus}, Math. Comput. 36, 587-592 (1981; Zbl 0493.12024)] and the Ben-Or algorithm [\textit{M. Ben-Or}, Probabilistic algorithms in finite fields, Proc. 22nd Annual Symp. Foundations of Computer Science, IEEE, 394-398 (1981)]. These are probabilistic algorithms that find a nontrivial zero-divisor \(u\) in \(F_q[x]/(f)\) and then use it to construct a proper factor of \(f\), namely \(\text{gcd} (u,f)\). The paper under review generalizes this approach. Assume that the given polynomial \(f\) is an equal-degree polynomial, as one always may. For an arbitrary polynomial \(\gamma \in F_q [x]\) and a nonempty set \(C \subseteq F_q\), choose a uniform random polynomial \(h \in F_q[x]\) and compute the gcd of \(f\) and \(\gamma (h) - c \text{mod} f\) for all \(c \in C\). The probability that these gcd computations will produce a proper factor of \(f\) is determined, and a characterization is presented for those sets \(C\) that yield the highest factorization probability, given \(\gamma\) and the cardinality of \(C\). Then, given the cardinality of \(C\), the least upper bound for the factorization probability among all choices of \(\gamma\) is computed. Finally, the author characterizes the polynomials \(\gamma\) and the corresponding sets \(C\) which achieve this least upper bound. It turns out that both the Cantor-Zassenhaus algorithm and the Ben-Or algorithm fall into this optimal category.