On computing factors of cyclotomic polynomials

Richard P. Brent
Computer Sciences Laboratory
Australian National University

In memory of
Derrick H. Lehmer
1905{1991

Abstract

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

4?n(x) = A2n ? (?1)(n?1)=2nB2n:

A similar identity of Aurifeuille, Le Lasseur and Lucas is

?n((?1)(n?1)=2x) = C2n ? nxD2n

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

??n=2(?x2) = C2n ? nxD2n;

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.
1991 Mathematics Subject Classification. Primary 11-04, 05A15; Secondary 11T06, 11T22, 11T24, 11Y16, 12-04, 12E10, 12Y05,

Key words and phrases. Aurifeuillian factorization, class number, cyclotomic field, cyclotomic polynomial, Dirichlet series, exact computation, Gauss's identities, generating functions, integer factorization, Lucas's identities, Newton's identities.

1 Introduction

For integer n > let ?n(x) denote the cyclotomic polynomial

?n(x) =
Y

<j<=n
(j;n)=1

(x ? ?j); (1)

where ? is a primitive n-th root of unity. Clearly

xn ? 1 =
Y

djn
?d(x); (2)

and the Mobius inversion formula [13] gives

?n(x) =
Y

djn
(xd ? 1)?(n=d): (3)