Faster factoring of integers of a special form

Abstract

. A speedup of Lenstra's Elliptic Curve Method of factorization is presented. The speedup works for integers of the form N = PQ^2 , where P is a prime sufficiently smaller than Q. The result is of interest to cryptographers, since integers with secret factorization of this form are being used in digital signatures. The algorithm makes use of what we call "Jacobi signatures". We believe these to be of independent interest. 1 Introduction It is not known how to efficiently factor a large integer N . Currently, the algorithm with best asymptotic complexity is the Number Field Sieve (see [6] ). For numbers below a certain size (currently believed to be about 120 integers), either the Quadratic Sieve [14] or the Elliptic Curve Method [7] are faster. Which of these algorithms to use depends on the size of N and of the smallest prime factor of N . When the size of the smallest factor is sufficiently smaller than p N , the Elliptic Curve Method is the fastest of the three. In this no...

Keywords

Related Publications