Speeding up the lattice factoring method

作     者：Uchiyama, S Kanayama, N 

作者机构：NTT Labs Yokosuka Kanagawa 2390847 Japan Waseda Univ Grad Sch Sci & Engn Tokyo 1698555 Japan 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (IEICE Trans Fund Electron Commun Comput Sci)

年 卷 期：2001年第E84A卷第1期

页      面：146-150页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：factoring problem LLL-algorithm lattice factoring method 

摘      要：Recently, Boneh et al. proposed an interesting algorithm for factoring integers, the so-called LFM (Lattice Factoring Method). It is based on the techniques 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 effective for large r. That is, it runs in polynomial time in log N when r is 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 considerations and experimental results are provided that show that the proposed algorithm offers shorter runing time than the original LFM.