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,
  • [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
    B. L. van der Waerden, Algebra. Vol. 2, Translated by John R. Schulenberger, Frederick Ungar Publishing Co., New York, 1970. MR 0263583
  • [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