Polynomial factorization: Sharp bounds, efficient algorithms (Q689110)

The paper shows that, in order to realize fast algorithms, it is necessary to control the size of the coefficients in one irreducible factor. A bound on this size is presented in Theorem 1. It makes use of the weighted norm and it is almost optimal. The paper shows how to use this bound in the process of \(p\)-adic lifting in such a way to obtain an efficient algorithm. A worked example completes the paper.