A Generalized Class of Polynomials that are Hard to Factor
Erich Kaltofen, David R. Musser, B. David Saunders · SIAM Journal on Computing · 1983
A class of univariate polynomials is defined which make the Berlekamp-Hensel factorization algorithm take an exponential amount of time. This class contains as subclasses the Swinnerton-Dyer polynomials discussed by Berlekamp and a subset of the cyclotomic polynomials. Aside from shedding light on the complexity of polynomial factorization this class is also useful in testing implementations of the Berlekamp–Hensel and related algorithms.