Factoring with cyclotomic polynomials

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, X2 + 1, and X2 ± X + 1. We show that one may take f to be Φk, the k-th cyclotomic polynomial. In constrast 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 Φk(p)) is bounded by a polynomial in k, logE, and logN.