Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields

We examine the problem of factoring the $r$th cyclotomic polynomial, $\Phi _r(x),$ over $\mathbb{F}_p$, $r$ and $p$ distinct primes. Given the traces of the roots of $\Phi _r(x)$ we construct the coefficients of $\Phi _r(x)$ in time $O(r^4)$. We demonstrate a deterministic algorithm for factoring $\Phi _r(x)$ in time $O((r^{1/2+\epsilon}\log p)^9)$ when $\Phi _r(x)$ has precisely two irreducible factors. Finally, we present a deterministic algorithm for computing the sum of the irreducible factors of $\Phi _r(x)$ in time $O(r^6)$.