Polynomial factorization algorithms
Algorithms over finite fields use Frobenius and linear algebra. Over the rationals, modular factorization, Hensel lifting and lattice reduction recover exact factors.
ArticleFactoring sparse polynomials
Sparse polynomials are encoded by their nonzero terms. Large exponents and dense factors make this a different algorithmic problem from dense factorization.
ArticleAlgorithms for Galois groups
Galois-group algorithms combine local factorizations, permutation groups and resolvents. Certification proves that the resulting subgroup is the full group.
ArticleReferences
- Factoring polynomials over finite fieldsBerlekamp, Elwyn R. · 1967
Factors polynomials over finite fields by linear algebra in the Frobenius-fixed subalgebra, which detects the irreducible factors.
- On Hensel factorization, IZassenhaus, Hans · 1969
The classical modular route to integer-polynomial factorization: factor modulo a prime, lift p-adically, then recombine the lifted factors. It explains why local factors must be grouped before recovering rational factors.
- Probabilistic algorithms in finite fieldsRabin, Michael O. · 1980
Develops finite-field algorithms for irreducible-polynomial construction, root finding, and factorization, alongside Frobenius-power tests for irreducibility of monic polynomials.
- A new algorithm for factoring polynomials over finite fieldsCantor, David G. and Zassenhaus, Hans · 1981
Gives a randomized finite-field factorization algorithm, including the splitting of products whose irreducible factors have equal degree. The search is randomized; the resulting factors can be checked exactly.
- Factoring polynomials with rational coefficientsLenstra, A. K. and Lenstra, Jr., H. W. and Lovász, L. · 1982
Proves polynomial-time factorization over the rationals using lattice basis reduction. The lattice algorithm also supports algebraic-relation searches and certificate construction.
Comments
Any comments are welcome. Comments appear after the site owner approves them. Privacy policy.