A high-performance algorithm for calculating cyclotomic polynomials
Andrew Arnold, Michael Monagan · 2010
The nth cyclotomic polynomial, Φn(z), is the monic polynomial whose ϕ(n) distinct roots are the nth primitive roots of unity. Φn(z) can be computed efficiently as a quotient of terms of the form (1 - zd) by way of a method the authors call the Sparse Power Series algorithm. We improve on this algorithm in three steps, ultimately deriving a fast, recursive algorithm to calculate Φn(z). The new algorithm, which we have implemented in C, allows us to compute Φn(z) for n > 109 in less than one minute.