Subject 10 / 12

Algorithms and certificates

algorithmIntermediateFinite fields, Q, and p-adic fields

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.

Article
methodResearchnumber fields and general coefficient fields

Factoring sparse polynomials

Sparse polynomials are encoded by their nonzero terms. Large exponents and dense factors make this a different algorithmic problem from dense factorization.

Article
algorithmIntermediateQ, number fields, and p-adic fields

Algorithms for Galois groups

Galois-group algorithms combine local factorizations, permutation groups and resolvents. Certification proves that the resulting subgroup is the full group.

Article

References

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.