Calculating cyclotomic polynomials
Andrew Arnold, Michael Monagan · Mathematics of Computation · 2011
We present three algorithms to calculate Φ n ( z ) \Phi _n(z) , the n t h n_{th} cyclotomic polynomial. The first algorithm calculates Φ n ( z ) \Phi _n(z) by a series of polynomial divisions, which we perform using the fast Fourier transform. The second algorithm calculates Φ n ( z ) \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 n for which the height of Φ n ( z ) \Phi _n(z) is greater than n n , n 2 n^2 , n 3 n^3 , and n 4 n^4 , respectively. The third algorithm, the big prime algorithm, generates the terms of Φ n ( z ) \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 k
Cited by 27 works. doi:10.1090/s0025-5718-2011-02467-1 Open-access PDF
Authors
References
- The On-Line Encyclopedia of Integer Sequences
- Modern computer algebra
- Algorithms for Computer Algebra
- Modern computer algebra
- On the coefficients of the cyclotomic polynomial
- On the Coefficients of the Cyclotomic Polynomials
- Flat cyclotomic polynomials of order three
- Vanishing sums of roots of unity
- Inverse cyclotomic polynomials
- On the size of the coefficients-of the cyclotomic polynomial