|
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 log p our algorithm runs in polynomial time (in log N). Hence, we obtain a new class of integers that can be eciently factored. When r p log p the algorithm is asymptotically faster than the Elliptic Curve Method. Our results suggest that integers of the form N = p r q should be used with care. This is especially true when r is large, namely r greater than, |
