Resource type

Thesis type

(Thesis) M.Sc.

Date created

2011-01-21

Authors/Contributors

Author: Arnold, Andrew David

Abstract

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.

Document

Identifier

etd6433

Copyright statement

Copyright is held by the author.

Scholarly level

Supervisor or Senior Supervisor

Thesis advisor: Monagan, Michael

Member of collection

Attachment | Size |
---|---|

etd6433_AArnold.pdf | 778.91 KB |