Speeding up the lattice factoring method

Recently, Boneh et al. proposed an interesting algorithm for factoring inte gers, the so-called LFM (Lattice Factoring Method). It is based on the tech niques of Coppersmith and Howgrave-Graham, namely, it cleverly employs the LLL-algorithm. The LFM is for integers of the form N = p(r)q, and is very e ffective for large r. That is, it runs in polynomial time in log N when r i s on the order of logp. We note that for small r, e.g. N = pq, p(2)q, it is an exponential time algorithm in log N. In this paper, we propose a method for speeding up the LFM from a practical viewpoint. Also, theoretical cons iderations and experimental results are provided that show that the propose d algorithm offers shorter runing time than the original LFM.