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)

 

Calculating cyclotomic polynomials


Authors: Andrew Arnold and Michael Monagan
Journal: Math. Comp. 80 (2011), 2359-2379
MSC (2010): Primary 11Y16; Secondary 12-04
Published electronically: February 17, 2011
MathSciNet review: 2813365
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present three algorithms to calculate $ \Phi_n(z)$, the $ n_{th}$ cyclotomic polynomial. The first algorithm calculates $ \Phi_n(z)$ by a series of polynomial divisions, which we perform using the fast Fourier transform. The second algorithm calculates $ \Phi_n(z)$ as a quotient of products of sparse power series. These two algorithms, described in detail in the paper, were used to calculate cyclotomic polynomials of large height and length. In particular, we have found the least $ n$ for which the height of $ \Phi_n(z)$ is greater than $ n$, $ n^2$, $ n^3$, and $ n^4$, respectively. The third algorithm, the big prime algorithm, generates the terms of $ \Phi_n(z)$ sequentially, in a manner which reduces the memory cost. We use the big prime algorithm to find the minimal known height of cyclotomic polynomials of order five. We include these results as well as other examples of cyclotomic polynomials of unusually large height, and bounds on the coefficient of the term of degree $ k$ for all cyclotomic polynomials.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 12-04

Retrieve articles in all journals with MSC (2010): 11Y16, 12-04


Additional Information

Andrew Arnold
Affiliation: Centre for Experimental and Constructive Mathematics, Simon Fraser University, Burnaby, BC V5A 1S6, Canada
Email: ada26@sfu.ca

Michael Monagan
Affiliation: Centre for Experimental and Constructive Mathematics, Simon Fraser University, Burnaby, BC V5A 1S6, Canada
Email: mmonagan@cecm.sfu.ca

DOI: http://dx.doi.org/10.1090/S0025-5718-2011-02467-1
PII: S 0025-5718(2011)02467-1
Received by editor(s): October 10, 2008
Received by editor(s) in revised form: July 17, 2010
Published electronically: February 17, 2011
Additional Notes: This work was supported by NSERC of Canada and the MITACS NCE of Canada
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.