Factoring N=prq for large r

Authors: D. Boneh, G. Durfee, and N. Howgrave-Graham

We present an algorithm for factoring integers of the form N=prq for large r. Such integers were previously proposed for various cryptographic applications. When r is close to log p our algorithm runs in polynomial time (in log N). Hence, we obtain a new class of integers that can be efficiently factored. When r is close to sqrt(log p) the algorithm is asymptotically faster than the Elliptic Curve Method. Our results suggest that integers of the form N=prq should be used with care. This is especially true when r is large, namely r greater than sqrt(log p).

In Proceedings Crypto '99, Lecture Notes in Computer Science, Vol. 1666, Springer-Verlag, pp. 326--337, 1999

Full paper: PostScript         [first posted 2/1999 ]