  For odd square-free n > 1 the n-th cyclotomic polynomial satisfies an
identity of Gauss. There are similar identity of Aurifeuille, Le Lasseur and
Lucas. These identities all involve certain 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 the
polynomials, and illustrate the application to integer factorization with some
numerical examples.
