Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On computing factors of cyclotomic polynomials

Author: Richard P. Brent
Journal: Math. Comp. 61 (1993), 131-149
MSC: Primary 11T22; Secondary 11Y05, 12Y05
MathSciNet review: 1205459
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For odd square-free $ n > 1$ the cyclotomic polynomial $ {\Phi _n}(x)$ satisfies the identity of Gauss,

$\displaystyle 4{\Phi _n}(x) = A_n^2 - {( - 1)^{(n - 1)/2}}nB_n^2.$

A similar identity of Aurifeuille, Le Lasseur, and Lucas is

$\displaystyle {\Phi _n}({( - 1)^{(n - 1)/2}}x) = C_n^2 - nxD_n^2$

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

$\displaystyle \pm {\Phi _{n/2}}( - {x^2}) = C_n^2 - nxD_n^2.$

Here, $ {A_n}(x), \ldots ,{D_n}(x)$ are polynomials with integer coefficients. We show how these coefficients can be computed by simple algorithms which require $ O({n^2})$ arithmetic operations and work over the integers. We also give explicit formulae and generating functions for $ {A_n}(x), \ldots ,{D_n}(x)$, and illustrate the application to integer factorization with some numerical examples.

References [Enhancements On Off] (What's this?)

  • [1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR 0413592
  • [2] A. Aurifeuille and H. Le Lasseur, see [20, p. 276] or [21, p. 785].
  • [3] N. G. W. H. Beeger, On a new quadratic form for certain cyclotomic polynomial, Nieuw Arch. Wiskunde (2) 23 (1951), 249–252. MR 0043132
  • [4] Richard P. Brent, Fred G. Gustavson, and David Y. Y. Yun, Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms 1 (1980), no. 3, 259–295. MR 604867, 10.1016/0196-6774(80)90013-9
  • [5] R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), no. 4, 581–595. MR 0520733
  • [6] R. P. Brent and H. J. J. te Riele, Factorizations of $ {a^n} \pm 1,13 \leq a < 100$, Report NM-R9212, Department of Numerical Mathematics, Centrum voor Wiskunde en Informatica, Amsterdam, June 1992.
  • [7] John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of 𝑏ⁿ±1, 2nd ed., Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, RI, 1988. 𝑏=2,3,5,6,7,10,11,12 up to high powers. MR 996414
  • [8] A. J. C. Cunningham, Factorisation of $ N = {y^y} \mp 1$ and $ {x^{xy}} \mp {y^{xy}}$, Messenger Math. (2) 45 (1915), 49-75.
  • [9] A. J. C. Cunningham and H. J. Woodall, Factorisation of $ {y^n} \mp 1,\;y = 2,3,5,6,7,10,11,12$ up to high powers (n), Hodgson, London, 1925.
  • [10] Harold Davenport, Multiplicative number theory, 2nd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York-Berlin, 1980. Revised by Hugh L. Montgomery. MR 606931
  • [11] P. G. Lejeune Dirichlet, Vorlesungen über Zahlentheorie, 4th ed., Chapter 5 and Supplement 7, Friedr. Vieweg & Sohn, Braunschweig, 1894.
  • [12] C. F. Gauss, Disquisitiones Arithmeticœ, G. Fleischer, Leipzig, 1801, Art. 356-357. Reprinted in Carl Friedrich Gauss Werke, Band 1, Georg Olms Verlag, Hildesheim, 1981.
  • [13] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., Chapter 16, Clarendon Press, Oxford, 1984.
  • [14] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
  • [15] M. Kraitchik, Décomposition de $ {a^n} \pm {b^n}$ en facteurs dans le cas où nab est un carré parfait avec une table des décompositions numériques pour toutes les valeurs de a et b inférieures à 100, Gauthier-Villars, Paris, 1922.
  • [16] -, Recherches sur la théorie des nombres, Vol. 1, Gauthier-Villars, Paris, 1924.
  • [17] -, Introduction à la théorie des nombres, Gauthiers-Villars, Paris, 1952.
  • [18] Edmund Landau, Vorlesungen über Zahlentheorie, Band 1(1): Aus der elementaren und additiven Zahlentheorie, Leipzig, 1927; English transl., Elementary number theory, Chelsea, New York, 1958.
  • [19] Serge Lang, Cyclotomic fields I and II, 2nd ed., Graduate Texts in Mathematics, vol. 121, Springer-Verlag, New York, 1990. With an appendix by Karl Rubin. MR 1029028
  • [20] E. Lucas, Théorèmes d'arithmétique, Atti. Roy. Acad. Sc. Torino 13 (1877-78), 271-284.
  • [21] -, Sur la série récurrente de Fermat, Bull. Bibl. Storia Sc. Mat. e Fis. 11 (1878), 783-789.
  • [22] -, Sur les formules de Cauchy et de Lejeune-Dirichlet, Ass. Française pour l'Avanc. des Sci., Comptes Rendus 7 (1878), 164-173.
  • [23] Hans Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics, vol. 57, Birkhäuser Boston, Inc., Boston, MA, 1985. MR 897531
  • [24] John Riordan, An introduction to combinatorial analysis, Princeton University Press, Princeton, N.J., 1980. Reprint of the 1958 edition. MR 580155
  • [25] A. Schinzel, On primitive prime factors of 𝑎ⁿ-𝑏ⁿ, Proc. Cambridge Philos. Soc. 58 (1962), 555–562. MR 0143728
  • [26] Peter Stevenhagen, On Aurifeuillian factorizations, Nederl. Akad. Wetensch. Indag. Math. 49 (1987), no. 4, 451–468. MR 922449
  • [27] H. W. Turnbull, Theory of equations, 5th ed., §32, Oliver and Boyd, Edinburgh, 1952.
  • [28] B. L. van der Waerden, Algebra. Vol 1, Translated by Fred Blum and John R. Schulenberger, Frederick Ungar Publishing Co., New York, 1970. MR 0263582
  • [29] Lawrence C. Washington, Introduction to cyclotomic fields, Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1982. MR 718674

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11T22, 11Y05, 12Y05

Retrieve articles in all journals with MSC: 11T22, 11Y05, 12Y05

Additional Information

Keywords: 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
Article copyright: © Copyright 1993 American Mathematical Society