Shoup V. A new Polynomial Factorization Algorithm and its Implementation

36 p.We consider the problem of factoring univariate polynomials over a nite eld. We demonstrate that the new baby step/giant step factoring method, recently developed by Kaltofen & Shoup, can be made into a very practical algorithm. We describe an implementation of this algorithm, and present the results of empirical tests comparing this new algorithm with others.
When factoring polynomials modulo large primes, the algorithm allows much larger polynomials to be factored using a reasonable amount of time and space than was previously possible.
For example, this new software has been used to factor a \generic" polynomial of degree 2048 modulo a 2048-bit prime in under 12 days on a Sun SPARC-station 10, using 68 MB of main memory.Iintoduction
Copmparison of factoring methods
Empirical results
Overview of algorithm
Distinct-degree factorization
Modular Composition
Saving space
Reducing the number of GCD computations
Equal-Degree Factorization
Trace Computation
Factor Extraction
Computing Minimum Polynomials
Power Pro jection
Berlekamp's Null-Space Method
Arithmetic in Fp
Arithmetic in Fp[x]
Polynomial Division
Computing Polynomial Inverses
Modular squaring
Pre-conditioned Modular Multiplication
Transposed Modular Multiplication
Computing GCD's
Multi-precision arithmetic
Single-precision modular arithmetic
Multi-precision/single-precision division
Chinese Remaindering
Experimental Results
Multi-precision Arithmetic
Arithmetic in Fp[x]
Modular Composition and Related Problems
Factoring Polynomials