Univariate Polynomial Rings [HB 44]

Polynomials over the integers or rationals are now factored by the exciting new algorithm of Mark van Hoeij (see the Handbook for details and references). The search for the correct combination of modular factors (which has exponential worst-case complexity in the standard Berlekamp-Zassenhaus algorithm) is now performed by van Hoeij's algorithm, which efficiently finds the correct combinations by solving a Knapsack problem via the LLL lattice-basis reduction algorithm.

van Hoeij's new algorithm is much more efficient in practice than the original lattice-based factoring algorithm proposed by Lenstra et al.: the lattice constructed in van Hoeij's algorithm has dimension equal to the number of modular factors (not the degree of the input polynomial), and the entries of the lattice are very much smaller. Many polynomials can now be easily factored which were out of reach for any previous algorithm (for example, the Swinnerton-Dyer polynomials).

New features:

• The function Polynomial allows the user to create a univariate polynomial without first having to create its parent polynomial ring.
• Automatic coercion has been improved to allow the case where a polynomial over a finite field is added to a rational constant.
• Factorization of polynomials over $\mbox{\bf Z}$ or $\mbox{\bf Q}$ has been greatly improved by the van Hoeij combination algorithm. Factorization over algebraic number fields has also been improved as a result.
• New function SwinnertonDyerPolynomial(n) to create the n-th Swinnerton-Dyer polynomial.
• New function EqualDegreeFactorization to compute the equal-degree factorization of a polynomial over a finite field which is known to be a product of distinct degree-d irreducibles alone.