Algorithms for computing cyclotomic polynomials

The $n$th cyclotomic polynomial, $\Phi_n(z)$, is the minimal polynomial of the $n$th primitive roots of unity. We developed algorithms for calculating $\Phi_n(z)$ to study its coefficients. The first approach computes $\Phi_n(z)$ using its discrete Fourier transform. The sparse power series (SPS) algorithm calculates $\Phi_n(z)$ as a truncated power series. We make three improvements to the SPS algorithm, ultimately resulting in a fast recursive variant of the SPS algorithm. We make further optimizations to this recursive SPS algorithm to compute cyclotomic polynomials that require large amounts of storage. These algorithms were used to find the least $n$ such that $\Phi_n(z)$ has height greater than $n^k$, for $k=1,2,...,7$. The big prime algorithm quickly computes $\Phi_n(z)$ for $n$ having a large prime divisor $p$. This algorithm was used to search for families of $\Phi_n(z)$ of height 1.