rpb127

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).

Abstract

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

Phi_n(x) = C_n² + nxD_n²

of Aurifeuille, Le Lasseur and Lucas. Here C_n(x) and D_n(x) are monic polynomials with integer coefficients. These coefficients can be computed by simple algorithms which require O(n²) arithmetic operations over the integers. Also, there are explicit formulas and generating functions for C_n(x) and D_n(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].

Comments

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