cl-banner

Polynomial Factorization

René Thiemann and Akihisa Yamada

Archive of Formal Proofs 2016.

Abstract

Based on existing libraries for polynomial interpolation and matrices, we formalized several factorization algorithms for polynomials, including Kronecker’s algorithm for integer polynomials, Yun’s square-free factorization algorithm for field polynomials, and Berlekamp’s algorithm for polynomials over finite fields. By combining the last one with Hensel’s lifting, we derive an efficient factorization algorithm for the integer polynomials, which is then lifted for rational polynomials by mechanizing Gauss’ lemma. Finally, we assembled a combined factorization algorithm for rational polynomials, which combines all the mentioned algorithms and additionally uses the explicit formula for roots of quadratic polynomials and a rational root test.
As side products, we developed division algorithms for polynomials over integral domains, as well as primality-testing and prime-factorization algorithms for integers.

 

  AFP entry

BibTeX 

@article{Polynomial_Factorization-AFP,
author = "Ren{\'e} Thiemann and Akihisa Yamada",
title = "Polynomial Factorization",
journal = "Archive of Formal Proofs",
year = 2016,
note = "{\url{http://afp.sf.net/entries/Polynomial_Factorization.shtml},
Formal proof development}"
}
Nach oben scrollen