GCD and Factorization

• Resultant, discriminant (sub-resultant algorithm, Euclidean algorithm)
• Greatest common divisor, extended greatest common divisor
• Extended greatest common divisor
• Hensel lift
• Square free factorization
• Distinct degree factorization
• Factorization over $\mbox{\rm GF}(q)$: Small field Berlekamp, large field Berlekamp, Shoup algorithms
• Factorization over $\mbox{\bf Z}$ and $\mbox{\bf Q}$: van Hoeij algorithm
• Factorization over $\mbox{\bf Q}_p$ and its extensions
• Factorization over $\mbox{\bf Q}(\alpha)$: Trager algorithm

Greatest common divisors for polynomials over Z are computed using either a modular algorithm or the GCD-HEU method, while for polynomials over a number field, the modular method is used. Factorization of polynomials over Z uses the exciting new algorithm of Mark van Hoeij, which efficiently finds the correct combinations of modular factors by solving a Knapsack problem via the LLL lattice-basis reduction algorithm.