Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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 Free Access

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?)


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
Email: filaseta@math.sc.edu

Andrzej Schinzel
Affiliation: Institute of Mathematics of the Polish Academy of Sciences, P.O. Box 137, ul. Śniadeckich 8, 00-950 Warszawa 10, Poland
Email: a.schinzel@impan.gov.pl

DOI: http://dx.doi.org/10.1090/S0025-5718-03-01589-8
PII: S 0025-5718(03)01589-8
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