On computing factors of cyclotomic polynomials

135. R. P. Brent, On computing factors of cyclotomic polynomials, Mathematics of Computation 61 (1993), 131-149 (D. H. Lehmer memorial issue). MR 93m:11131. Also appeared as Technical Report TR-CS-92-13, September 1992, 21 pp. arXiv:1004.5466v1

Abstract: dvi (3K), pdf (80K), ps (29K).

Paper: pdf (1446K).

Technical Report: dvi (34K), pdf (253K), ps (118K).


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

4Phin(x)  =  An2  -  (-1)(n-1)/2nBn2.

A similar identity of Aurifeuille, Le Lasseur and Lucas is

Phin((-1)(n-1)/2x)  =  Cn2  -  nxDn2

or, in the case that n is even and square-free,

+Phin/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.


For a more expository version with additional numerical examples, see [127].

Go to next publication

Return to Richard Brent's index page