Using the theory of cyclotomy to factor cyclotomic polynomials over finite fields
Greg Stein · Mathematics of Computation · 2000
We examine the problem of factoring the r r th cyclotomic polynomial, Φ r ( x ) , \Phi _r(x), over F p \mathbb {F}_p , r r and p p distinct primes. Given the traces of the roots of Φ r ( x ) \Phi _r(x) we construct the coefficients of Φ r ( x ) \Phi _r(x) in time O ( r 4 ) O(r^4) . We demonstrate a deterministic algorithm for factoring Φ r ( x ) \Phi _r(x) in time O ( ( r 1 / 2 + ϵ log p ) 9 ) O((r^{1/2+\epsilon }\log p)^9) when