Algorithms for Computing Cyclotomic Polynomials.

Andrew Arnold, Simon Fraser University.


Friday January 21st, in K9509 at 12:30pm.


   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.