Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant

We show an improvement of the known best deterministic approach to factorization of a univariate polynomial p(x) over the complex field. Previously, such an improvement was achieved by means of a random perturbation of the coefficients of the input polynomial. We now apply some new techniques, which lead to a similar result without any randomization. The approach is unusual in exploiting some properties of the resultant of p(x) and p′(x), which is completely distinct from the techniques usually applied in order to compute complex polynomial factorization.