Abstract: dvi (3K), pdf (80K), ps (29K).
Paper: pdf (1446K).
Technical Report: dvi (34K), pdf (253K), ps (118K).
4Phi_{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,
+Phi_{n/2}(-x^{2}) = C_{n}^{2} - nxD_{n}^{2}.
Here A_{n}(x), ... , 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), ... , D_{n}(x), and illustrate the application to integer factorization with some numerical examples.