Factoring with cyclotomic polynomials

Publisher Website
Google Scholar
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.

This publication has 15 references indexed in Scilit: