Abstract: dvi (3K), pdf (80K), ps (29K).
Paper: pdf (1446K).
Technical Report: dvi (34K), pdf (253K), ps (118K).
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.
Go to next publication
Return to Richard Brent's index page