Algorithms for Computing Cyclotomic Polynomials.
Andrew Arnold, Simon Fraser University.
Abstract. The n'th cyclotomic polynomial, $\Phi_n(z)$, is the minimal polynomial of the n'th primitive roots of unity. We developed and implemented algorithms for calculating $\Phi_n(z)$ to study its coefficients. The first approach computes $\Phi_n(z)$ using the discrete Fourier transform. The sparse power series (SPS) algorithm calculates $\Phi_n(z)$ as a truncated power series. We make hree key 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 wthat require very 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 $1 \le k \le 7$. The big primie 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.