Factoring with cyclotomic polynomials

Authors:
Eric Bach and Jeffrey Shallit

Journal:
Math. Comp. **52** (1989), 201-219

MSC:
Primary 11Y05; Secondary 12-04, 68Q40

DOI:
https://doi.org/10.1090/S0025-5718-1989-0947467-1

MathSciNet review:
947467

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper discusses some new integer factoring methods involving cyclotomic polynomials.

There are several polynomials known to have the following property: given a multiple of , we can quickly split any composite number that has *p* as a prime divisor. For example--taking to be --a multiple of will suffice to easily factor any multiple of *p*, using an algorithm of Pollard. Other methods (due to Guy, Williams, and Judd) make use of , , and .

We show that one may take *f* to be , the *k*th cyclotomic polynomial. In contrast to the ad hoc methods used previously, we give a universal construction based on algebraic number theory that subsumes all the above results. Assuming generalized Riemann hypotheses, the expected time to factor *N* (given a multiple *E* of ) is bounded by a polynomial in *k*, , and .

**[1]**Eric Bach, Gary Miller, and Jeffrey Shallit,*Sums of divisors, perfect numbers and factoring*, SIAM J. Comput.**15**(1986), no. 4, 1143–1154. MR**861378**, https://doi.org/10.1137/0215083**[2]**E. Bach & J. Shallit,*A Class of Functions Equivalent to Factoring*, Technical Report 84-008, Department of Computer Science, University of Chicago, 1984.**[3]**Elwyn R. Berlekamp,*Algebraic coding theory*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR**0238597****[4]**John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr.,*Factorizations of 𝑏ⁿ±1*, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. 𝑏=2,3,5,6,7,10,11,12 up to high powers. MR**715603****[5]**John D. Dixon,*Factorization and primality tests*, Amer. Math. Monthly**91**(1984), no. 6, 333–352. MR**750520**, https://doi.org/10.2307/2322136**[6]**J. W. Cassels & A. Fröhlich,*Algebraic Number Theory*, Academic Press, London, 1976.**[7]**Carl Friedrich Gauss,*Disquisitiones arithmeticae*, Springer-Verlag, New York, 1986. Translated and with a preface by Arthur A. Clarke; Revised by William C. Waterhouse, Cornelius Greither and A. W. Grootendorst and with a preface by Waterhouse. MR**837656****[8]**Richard K. Guy,*How to factor a number*, Proceedings of the Fifth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1975) Utilitas Math. Publ., Winnipeg, Man., 1976, pp. 49–89. Congressus Numerantium, No. XVI. MR**0404120****[9]**D. Hilbert,*Die Theorie der algebraischen Zahlkörper*, Jahresbericht der Deutschen Mathematikervereinigung, vol. 4, 1897, pp. 175-546. [This has been reprinted in vol. 1 of Hilbert's collected works by Chelsea, 1981.]**[10]**J. C. Lagarias and A. M. Odlyzko,*Effective versions of the Chebotarev density theorem*, Algebraic number fields: 𝐿-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR**0447191****[11]**J. C. Lagarias, H. L. Montgomery, and A. M. Odlyzko,*A bound for the least prime ideal in the Chebotarev density theorem*, Invent. Math.**54**(1979), no. 3, 271–296. MR**553223**, https://doi.org/10.1007/BF01390234**[12]**Serge Lang,*Algebra*, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR**0197234****[13]**Serge Lang,*Algebraic number theory*, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR**0282947****[14]**H. W. Lenstra Jr.,*Primality testing algorithms (after Adleman, Rumely and Williams)*, Bourbaki Seminar, Vol. 1980/81, Lecture Notes in Math., vol. 901, Springer, Berlin-New York, 1981, pp. 243–257. MR**647500****[15]**H. W. Lenstra Jr.,*Factoring integers with elliptic curves*, Ann. of Math. (2)**126**(1987), no. 3, 649–673. MR**916721**, https://doi.org/10.2307/1971363**[16]**Daniel A. Marcus,*Number fields*, Springer-Verlag, New York-Heidelberg, 1977. Universitext. MR**0457396****[17]**Gary L. Miller,*Riemann’s hypothesis and tests for primality*, J. Comput. System Sci.**13**(1976), no. 3, 300–317. MR**480295**, https://doi.org/10.1016/S0022-0000(76)80043-8**[18]**Eugen Netto,*Ueber die Factorenzerlegung der Discriminanten algebraischer Gleichungen*, Math. Ann.**24**(1884), no. 4, 579–587 (German). MR**1510293**, https://doi.org/10.1007/BF01447450**[19]**J. M. Pollard,*Theorems on factorization and primality testing*, Proc. Cambridge Philos. Soc.**76**(1974), 521–528. MR**354514**, https://doi.org/10.1017/s0305004100049252**[20]**C.-P. Schnorr and H. W. Lenstra Jr.,*A Monte Carlo factoring algorithm with linear storage*, Math. Comp.**43**(1984), no. 167, 289–311. MR**744939**, https://doi.org/10.1090/S0025-5718-1984-0744939-5**[21]**H. M. Stark,*Some effective cases of the Brauer-Siegel theorem*, Invent. Math.**23**(1974), 135–152. MR**342472**, https://doi.org/10.1007/BF01405166**[22]**H. C. Williams,*A generalization of Lehmer’s functions*, Acta Arith.**29**(1976), no. 4, 315–341. MR**412091**, https://doi.org/10.4064/aa-29-4-315-341**[23]**H. C. Williams,*A 𝑝+1 method of factoring*, Math. Comp.**39**(1982), no. 159, 225–234. MR**658227**, https://doi.org/10.1090/S0025-5718-1982-0658227-7**[24]**H. C. Williams and J. S. Judd,*Determination of the primality of 𝑁 by using factors of 𝑁²±1*, Math. Comp.**30**(1976), no. 133, 157–172. MR**396390**, https://doi.org/10.1090/S0025-5718-1976-0396390-3**[25]**H. C. Williams and J. S. Judd,*Some algorithms for prime testing using generalized Lehmer functions*, Math. Comp.**30**(1976), no. 136, 867–886. MR**414473**, https://doi.org/10.1090/S0025-5718-1976-0414473-6**[26]**B. L. van der Waerden,*Modern Algebra*, Ungar, New York, 1950. [The relevant material on cyclotomic periods does not appear in the second English edition.]**[27]**Lawrence C. Washington,*Introduction to cyclotomic fields*, Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1982. MR**718674****[28]**B. F. Wyman,*What is a reciprocity law?*, Amer. Math. Monthly**79**(1972), 571–586; correction, ibid. 80 (1973), 281. MR**308084**, https://doi.org/10.2307/2317083

Retrieve articles in *Mathematics of Computation*
with MSC:
11Y05,
12-04,
68Q40

Retrieve articles in all journals with MSC: 11Y05, 12-04, 68Q40

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1989-0947467-1

Keywords:
Factorization,
cyclotomic fields

Article copyright:
© Copyright 1989
American Mathematical Society