On Computing Factors of Cyclotomic Polynomials
Richard P. Brent · Mathematics of Computation · 1993
For odd square-free $n > 1$ the cyclotomic polynomial ${\Phi _n}(x)$ satisfies the identity of Gauss, \[ 4{\Phi _n}(x) = A_n^2 - {( - 1)^{(n - 1)/2}}nB_n^2.\] A similar identity of Aurifeuille, Le Lasseur, and Lucas is \[ {\Phi _n}({( - 1)^{(n - 1)/2}}x) = C_n^2 - nxD_n^2\] or, in the case that n is even and square-free, \[ \pm {\Phi _{n/2}}( - {x^2}) = C_n^2 - nxD_n^2.\] Here, ${A_n}(x), \ldots ,{D_n}(x)$ are polynomials with integer coefficients. We show how these coefficients can be computed by simple algorithms which require $O({n^2})$ arithmetic operations and work over the integers. We also give explicit formulae and generating functions for ${A_n}(x), \ldots ,{D_n}(x)$, and illustrate the application to integer factorization with some numerical examples.