Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On testing the divisibility of lacunary polynomials by cyclotomic polynomials

Authors: Michael Filaseta and Andrzej Schinzel
Journal: Math. Comp. 73 (2004), 957-965
MSC (2000): Primary 13P05, 12Y05, 11Y16, 11C08
Published electronically: August 5, 2003
MathSciNet review: 2031418
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

References [Enhancements On Off] (What's this?)

  • 1. J. H. Conway and A. J. Jones, Trigonometric diophantine equations (On vanishing sums of roots of unity), Acta Arith. 30 (1976), 229-240. MR 54:10141

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 13P05, 12Y05, 11Y16, 11C08

Retrieve articles in all journals with MSC (2000): 13P05, 12Y05, 11Y16, 11C08

Additional Information

Michael Filaseta
Affiliation: Department of Mathematics, University of South Carolina, Columbia, South Carolina 29218

Andrzej Schinzel
Affiliation: Institute of Mathematics of the Polish Academy of Sciences, P.O. Box 137, ul. Śniadeckich 8, 00-950 Warszawa 10, Poland

Received by editor(s): October 1, 1998
Received by editor(s) in revised form: December 15, 2002
Published electronically: August 5, 2003
Additional Notes: The first author gratefully acknowledges support from the National Security Agency and the National Science Foundation
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society