Algorithms for computing cyclotomic polynomials

Resource type
Thesis type
(Thesis) M.Sc.
Date created
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.
Copyright statement
Copyright is held by the author.
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Monagan, Michael
Member of collection
Attachment Size
etd6433_AArnold.pdf 778.91 KB