#
Factoring *N=p*^{r}q for large *r*

^{r}q

**Authors:**

*D. Boneh, G. Durfee, and N. Howgrave-Graham*

** Abstract: **

We present an algorithm for factoring integers of the form
*N=p ^{r}q* 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=p*should be used with care. This is especially true when

^{r}q*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 ]