Speeding up the Lattice Factoring Method : Special Section on Cryptography and Information Security

スポンサーリンク

概要

• 論文の詳細を見る

• 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^rq, and is very effective for large r. That is, it runs in polynomial time in log N when r is on the order of log p. We note that for small r, e.g. N = pq, p^2q, 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 tunning time than the original LFM.

• 社団法人電子情報通信学会の論文
• 2001-01-01

著者

• Kanayama Naoki

  The Author Is With The Graduate School Of Science & Engineering Waseda University

• UCHIYAMA Shigenori

  The authors are with NTT Information Sharing Plat-form Laboratories, NTT Corporation

• Uchiyama Shigenori

  The Author Is With Ntt Laboratories

関連論文

• A New Factoring Method of Integers N = p^r x q for Large r(Special Section on Discrete Mathematics and Its Applications)
• Speeding up the Lattice Factoring Method : Special Section on Cryptography and Information Security

スポンサーリンク