Factoring \(N=p^rq\) for large \(r\). (English) Zbl 1007.11077

Wiener, Michael (ed.), Advances in cryptology - CRYPTO ’99. 19th annual international cryptology conference Santa Barbara, CA, USA, August 15-19, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1666, 326-337 (1999).
Summary: We present an algorithm for factoring integers of the form \(N= p^rq\) for large \(r\). Such integers were previously proposed for various cryptographic applications. When \(r\approx \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\approx \sqrt{\log p}\) the algorithm is asymptotically faster than the elliptic curve method. Our results suggest that integers of the form \(N= p^rq\) should be used with care. This is especially true when \(r\) is large, namely \(r\) greater than \(\sqrt{\log p}\).
For the entire collection see [Zbl 0921.00042].


11Y05 Factorization
94A60 Cryptography