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$, ${X^2} + 1$, and ${X^2} \pm X + 1$. We show that one may take f to be ${\Phi _k}$, the kth 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$.