#### 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.

#### Publication Info

Published in *Mathematics of Computation*, Volume 73, Issue 246, 2003, pages 957-965.

© Mathematics of Computation 2003, American Mathematical Society

Filaseta, M., & Schinzel, A. (2003). On testing the divisibility of lacunary polynomials by cyclotomic polynomials. *Mathematics Of Computation*, *73*(246), 957-965. http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01589-8/S0025-5718-03-01589-8.pdf