On testing the divisibility of lacunary polynomials by cyclotomic polynomials
Michael A. Filaseta, Andrzej Schinzel · Mathematics of Computation · 2003
An algorithm is described that determines whether a given polynomial with integer coefficients has a cyclotomic factor. The algorithm is intended to be used for sparse polynomials given as a sequence of coefficient-exponent pairs. A running analysis shows that, for a fixed number of nonzero terms, the algorithm runs in polynomial time.