Fast modular algorithms for squarefree factorization and Hermite integration (Q5929733)

The author gives modular algorithms for the squarefree factorization of primitive polynomials in \({\mathbb Z}[x]\) and for the computation of the rational part of the integral of a rational function over \({\mathbb Q}\). The motivation for this paper is the method of Hermite for the integration of rational functions [Nouv. Ann. (2) 11, 145-148 (1872; JFM 04.0125.04)], which requires squarefree factorization. The algorithms involve many techniques as partial fraction decompositions, subresultants, rational number reconstruction, inequalities on norms of polynomials, functions on prime numbers. We notice that the costs of the algorithms are computed and the implementation of the algorithm of modular Hermite reduction is presented. There is a relevant discussion concerning examples.