Title

On Testing the Divisibility of Lacunary Polynomials by Cyclotomic Polynomials

Document Type

Article

Subject Area(s)

Mathematics

Abstract

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 coefficientexponent pairs. A running analysis shows that, for a fixed number of nonzero terms, the algorithm runs in polynomial time.

Share

COinS