On computing factors of cyclotomic polynomials

Abstract

For odd square-free n > 1 the cyclotomic polynomial Φn(x) satisfies the identity of Gauss, 4Φ(x)=An2-(-1)(n-1)/2nBn2A similar identity of Aurifeuille, Le Lasseur, and Lucas is Φ((-1)(n-1)/2x)=Cn2-nxDn2or, in the case that n is even and square-free, ±Φn/2(-x2)=Cn2-nxDn2.Here, An(x), …, Dn(x) are polynomials with integer coefficients. We show how these coefficients can be computed by simple algorithms which require O(n2) arithmetic operations and work over the integers. We also give explicit formulae and generating functions for An(x), …, Dn(x) and illustrate the application to integer factorization with some numerical examples. Show more