rpb135

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

Abstract

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

4Phi_n(x) = A_n² - (-1)^(n-1)/2nB_n².

A similar identity of Aurifeuille, Le Lasseur and Lucas is

Phi_n((-1)^(n-1)/2x) = C_n² - nxD_n²

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

+Phi_n/2(-x²) = C_n² - nxD_n².

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

Comments

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

Go to next publication

Return to Richard Brent's index page