Factoring polynomials over global fields (Q1032662): Difference between revisions

The authors improve on \textit{M. van Hoeij}'s earlier algorithm for factoring polynomials [J. Number Theory 95, 167--189 (2002; Zbl 1081.11080)]. The new algorithm is shown to run in polynomial time for polynomials over the rational numbers \(\mathbb{Q}\) and over rational function fields with finite constant field \({\mathbb{F}}_{q}\). One essential idea is to work with logarithmic derivatives of polynomials \(g(X)\) rather than with power sums of their zeros. (We recall that the \(i\)-th trace \(\text{Tr}_i(g)\) is the sum of the \(i\)-th powers of the zeros of \(g\) and that \(g'/g\) equals the sum of \(\text{Tr}_i(g)X^{-i-1}\) over all non-negative indices \(i\).) This simplifies complexity proofs and also has practical algorithmic advantages. Following the introduction and some notations the authors give a survey on their algorithm for global fields \(K\). In the final two sections they consider the special cases \(K={\mathbb{F}}_{q} (t)\) and \(K=\mathbb{Q}\). Descriptions of the corresponding factoring algorithms and explicit complexity proofs are given. Also, ideas for variants/improvements and -- in case \(K=\mathbb{Q}\) -- comparisons with earlier algorithms are presented in some detail.