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