Improved dense multivariate polynomial factorization algorithms (Q2457431)

The author addresses computational complexity issues related with the factorization of multivariate polynomials, a classical problem in computer algebra. First, a deterministic algorithm is described in section 1.2 to reduce the problem of multivariate factorization to the univariate case, generalizing a lifting and recombination technique previously proposed by the author. Second, a probabilistic algorithm is described in section 1.3 for reduction to the bivariate case. In section 2 the author estimates the probability of success of the probabilistic reduction algorithm, thanks to upper bounds on the density of bad points (for which the reduction fails). Finally, the paper contains detailed errata for the papers [\textit{A. Bostan, G. Lecerf, B. Salvy, E. Schost} and \textit{B. Wiebelt}, ISSAC 2004. Proc. 2004 int. symp. symbolic and algebraic computation, Santander, Spain, July 4--7, 2004, 42--49 (2004; Zbl 1134.68595)] and [\textit{G. Lecerf}, Math. Comput. 75, 921--933 (2006; Zbl 1125.12003)].