Abstract

We formalize the Berlekamp–Zassenhaus algorithm for factoring square-free integer polynomials in Isabelle/HOL. We further adapt an existing formalization of Yun’s square-free factorization algorithm to integer polynomials, and thus provide an efficient and certified factorization algorithm for arbitrary univariate polynomials.
The algorithm first performs a factorization in the prime field GF(p) and then performs computations in the ring of integers modulo p^k, where both p and k are determined at runtime. Since a natural modeling of these structures via dependent types is not possible in Isabelle/HOL, we formalize the whole algorithm using Isabelle’s recent addition of local type definitions.
Through experiments we verify that our algorithm factors polynomials of degree 100 within seconds.

BibTeX

@inproceedings{JoostenCPP2017,
 author    = {Jos{\'{e}} Divas{\'{o}}n and Sebastiaan J. C. Joosten and Ren{\'{e}} Thiemann and Akihisa Yamada},
 title     = {A Formalization of the {B}erlekamp--{Z}assenhaus Factorization Algorithm},
 booktitle   = {Proceedings of the 6th ACM SIGPLAN Conference on Certified Programs and Proofs},
 series = {CPP 2017},
 year = {2017},
 isbn = {978-1-4503-4705-1},
 location = {Paris, France},
 pages = {17--29},
 numpages = {13},
 url = {http://doi.acm.org/10.1145/3018610.3018617},
 doi = {10.1145/3018610.3018617},
 acmid = {3018617},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Isabelle, Polynomial Factorization, Prime Fields}
}