Factoring N=prq for large rAuthors: 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 ]