## Factoring with cyclotomic polynomials

HTML articles powered by AMS MathViewer

- by Eric Bach and Jeffrey Shallit PDF
- Math. Comp.
**52**(1989), 201-219 Request permission

## Abstract:

This paper discusses some new integer factoring methods involving cyclotomic polynomials. There are several polynomials $f(X)$ known to have the following property: given a multiple of $f(p)$, we can quickly split any composite number that has*p*as a prime divisor. For example—taking $f(X)$ to be $X - 1$ —a multiple of $p - 1$ 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 $X + 1$, ${X^2} + 1$, and ${X^2} \pm X + 1$. We show that one may take

*f*to be ${\Phi _k}$, 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 ${\Phi _k}(p)$) is bounded by a polynomial in

*k*, $\log E$, and $\log N$.

## References

- 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**, DOI 10.1137/0215083
E. Bach & J. Shallit, - Elwyn R. Berlekamp,
*Algebraic coding theory*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR**0238597** - John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr.,
*Factorizations of $b^{n}\pm 1$*, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. $b=2,\,3,\,5,\,6,\,7,\,10,\,11,\,12$ up to high powers. MR**715603** - John D. Dixon,
*Factorization and primality tests*, Amer. Math. Monthly**91**(1984), no. 6, 333–352. MR**750520**, DOI 10.2307/2322136
J. W. Cassels & A. Fröhlich, - 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** - Richard K. Guy,
*How to factor a number*, Proceedings of the Fifth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1975) Congressus Numerantium, No. XVI, Utilitas Math. Publ., Winnipeg, Man., 1976, pp. 49–89. MR**0404120**
D. Hilbert, - J. C. Lagarias and A. M. Odlyzko,
*Effective versions of the Chebotarev density theorem*, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR**0447191** - 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**, DOI 10.1007/BF01390234 - Serge Lang,
*Algebra*, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR**0197234** - Serge Lang,
*Algebraic number theory*, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR**0282947** - 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** - H. W. Lenstra Jr.,
*Factoring integers with elliptic curves*, Ann. of Math. (2)**126**(1987), no. 3, 649–673. MR**916721**, DOI 10.2307/1971363 - Daniel A. Marcus,
*Number fields*, Universitext, Springer-Verlag, New York-Heidelberg, 1977. MR**0457396** - Gary L. Miller,
*Riemann’s hypothesis and tests for primality*, J. Comput. System Sci.**13**(1976), no. 3, 300–317. MR**480295**, DOI 10.1016/S0022-0000(76)80043-8 - Eugen Netto,
*Ueber die Factorenzerlegung der Discriminanten algebraischer Gleichungen*, Math. Ann.**24**(1884), no. 4, 579–587 (German). MR**1510293**, DOI 10.1007/BF01447450 - J. M. Pollard,
*Theorems on factorization and primality testing*, Proc. Cambridge Philos. Soc.**76**(1974), 521–528. MR**354514**, DOI 10.1017/s0305004100049252 - 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**, DOI 10.1090/S0025-5718-1984-0744939-5 - H. M. Stark,
*Some effective cases of the Brauer-Siegel theorem*, Invent. Math.**23**(1974), 135–152. MR**342472**, DOI 10.1007/BF01405166 - H. C. Williams,
*A generalization of Lehmer’s functions*, Acta Arith.**29**(1976), no. 4, 315–341. MR**412091**, DOI 10.4064/aa-29-4-315-341 - H. C. Williams,
*A $p+1$ method of factoring*, Math. Comp.**39**(1982), no. 159, 225–234. MR**658227**, DOI 10.1090/S0025-5718-1982-0658227-7 - H. C. Williams and J. S. Judd,
*Determination of the primality of $N$ by using factors of $N^{2}\pm 1$*, Math. Comp.**30**(1976), no. 133, 157–172. MR**396390**, DOI 10.1090/S0025-5718-1976-0396390-3 - 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**, DOI 10.1090/S0025-5718-1976-0414473-6
B. L. van der Waerden, - Lawrence C. Washington,
*Introduction to cyclotomic fields*, Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1982. MR**718674**, DOI 10.1007/978-1-4684-0133-2 - B. F. Wyman,
*What is a reciprocity law?*, Amer. Math. Monthly**79**(1972), 571–586; correction, ibid. 80 (1973), 281. MR**308084**, DOI 10.2307/2317083

*A Class of Functions Equivalent to Factoring*, Technical Report 84-008, Department of Computer Science, University of Chicago, 1984.

*Algebraic Number Theory*, Academic Press, London, 1976.

*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.]

*Modern Algebra*, Ungar, New York, 1950. [The relevant material on cyclotomic periods does not appear in the second English edition.]

## Additional Information

- © Copyright 1989 American Mathematical Society
- 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