Computing Aurifeuillian factors

127. R. P. Brent, Computing Aurifeuillian factors, in Computational Algebra and Number Theory (edited by W. Bosma and A. van der Poorten), Mathematics and its Applications, vol. 325, Kluwer Academic Publishers, Boston, 1995, 201-212. MR 96m:11111, 96c:00019.

Abstract: dvi (3K), pdf (70K), ps (26K).

Paper: dvi (20K), pdf (174K), ps (73K).


For odd square-free n > 1, the cyclotomic polynomial Phin(x) satisfies an identity

Phin(x)  =  Cn2  +  nxDn2

of Aurifeuille, Le Lasseur and Lucas. Here Cn(x) and Dn(x) are monic polynomials with integer coefficients. These coefficients can be computed by simple algorithms which require O(n2) arithmetic operations over the integers. Also, there are explicit formulas and generating functions for Cn(x) and Dn(x). This paper is a preliminary report which states the results for the case n = 1 mod 4, and gives some numerical examples. The proofs, generalisations to other square-free n, and similar results for the identities of Gauss and Dirichlet, will appear in [135].


For a more comprehensive (but more difficult) paper on the same topic, see [135].

Go to next publication

Return to Richard Brent's index page