Univariate polynomial factorization
Vilmar Trevisan · 1992
In an effort to establish state-of-the-art factorization routines, algorithms for factoring univariate polynomials are developed, analyzed and implemented in this thesis. The foundation of such algorithms lies in the efficient factorization over finite fields. Several finite-field factorization algorithms are compared and a hybrid algorithm that combine the strengths of the different approaches is devised. A result that expedite factorization over algebraic extension of finite fields is also presented. An almost optimal coefficient bound for factors of an integral polynomial is obtained. Unlike an overall bound, the new bound is a quantity that estimates the size of the coefficients of a single factor when the given polynomial is reducible. Effective use of the bound results in a more efficient polynomial factorization algorithm for integral polynomials. Fewer p-adic lifting steps are necessary to refine the factors to the prescribed accuracy. Additionally, the coefficient recovery for non-monic polynomials is obtained at an earlier stage. The factor recovery technique recommended merges the advantages of the best known methods. The single-factor bound also enables the introduction of a new, more efficient, combinatorial search algorithm for obtaining all true factors. The resulting univariate polynomial factoring algorithms are implemented and experimental data, along with machine timings, are presented.