Factoring very-high-degree polynomials
Gary A. Sitton, C.S. Burrus, James W. Fox, Sven Treitel · IEEE Signal Processing Magazine · 2003
In this article, we discuss the current status of polynomial factoring (root finding) algorithms with some historical and mathematical background including size limits, convergence, accuracy and speed. The methods of root approximation versus root refinement are also examined. We then focus on two improved general purpose computational techniques, and in particular the factorization algorithm by Lindsey-Fox (L-F), which makes use of the fast Fourier transform to factor polynomials with random coefficients of degrees as high as 1 million. Computer simulations give insight that result in significant improvements in traditional approaches to an ancient problem.