
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 squarefree 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 squarefree,
??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 1104, 05A15; Secondary 11T06, 11T22,
11T24, 11Y16, 1204, 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 nth 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)