Factoring N=prq for large r
Authors: D. Boneh, G. Durfee, and N. Howgrave-Graham
Abstract:
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).
Reference:
In Proceedings Crypto '99, Lecture Notes in Computer Science, Vol. 1666, Springer-Verlag, pp. 326--337, 1999
Full paper: PostScript [first posted 2/1999 ]