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
DOI: https://doi.org/10.1090/S0025-5718-1993-1205459-2
MathSciNet review: 1205459
Full-text PDF

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] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms, Chapter 8, Addison-Wesley, Menlo Park, CA, 1974. MR 0413592 (54:1706)
  • [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 polynomials, Nieuw Arch. Wisk. (2) 23 (1951), 249-252. MR 0043132 (13:211c)
  • [4] R. P. Brent, F. G. Gustavson, and D. Y. Y. Yun, Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms 1 (1980), 259-295. MR 604867 (82d:65033)
  • [5] R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), 581-595. MR 0520733 (58:25090)
  • [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] J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., Factorizations of $ {b^n} \pm 1,\;b = 2,3,5,6,7,10,11,12$ up to high powers, 2nd ed., Amer. Math. Soc., Providence, RI, 1988. MR 996414 (90d:11009)
  • [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] H. Davenport, Multiplicative number theory, 2nd ed. (revised by H. L. Montgomery), Springer-Verlag, New York, 1980. MR 606931 (82m:10001)
  • [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] D. E. Knuth, The art of computer programming, Volume 2: Seminumerical algorithms, 2nd ed., Chapter 3, Addison-Wesley, Menlo Park, CA, 1981. MR 633878 (83i:68003)
  • [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, II, combined 2nd ed., Graduate Texts in Math., vol. 126, Springer-Verlag, New York, 1990. MR 1029028 (91c:11001)
  • [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, Birkhäuser, Boston, 1985. MR 897531 (88k:11002)
  • [24] John Riordan, An introduction to combinatorial analysis, Chapter 2, Exercise 27, Princeton Univ., Princeton, New Jersey, 1978. MR 580155 (81e:05002)
  • [25] A. Schinzel, On the primitive prime factors of $ {a^n} - {b^n}$, Proc. Cambridge Philos. Soc. 58 (1962), 555-562. MR 0143728 (26:1280)
  • [26] Peter Stevenhagen, On Aurifeuillian factorizations, Nederl. Akad. Wetensch. Indag. Math. 49 (1987), 451-468. MR 922449 (89a:11015)
  • [27] H. W. Turnbull, Theory of equations, 5th ed., §32, Oliver and Boyd, Edinburgh, 1952.
  • [28] B. L. van der Waerden, Algebra, Vol. 1, Chapter 7 (English transl. by Fred Blum, 5th ed.), Frederick Ungar, New York, 1953. MR 0263582 (41:8187a)
  • [29] L. C. Washington, Introduction to cyclotomic fields, Graduate Texts in Math., vol. 83, Springer-Verlag, New York, 1982. MR 718674 (85g:11001)

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

DOI: https://doi.org/10.1090/S0025-5718-1993-1205459-2
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

American Mathematical Society