On Testing the Divisibility of Lacunary Polynomials by Cyclotomic Polynomials

Author(s)

Michael Filaseta, University of South Carolina - ColumbiaFollow
Andrzej Schinzel

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.

Rights

© 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