The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Baru-baru ini, Boneh et al. mencadangkan satu algoritma yang menarik untuk pemfaktoran integer, yang dipanggil LFM (Lattice Factoring Method). Ia berdasarkan teknik Coppersmith dan Howgrave-Graham, iaitu, ia menggunakan algoritma LLL dengan bijak. LFM adalah untuk integer borang N = pr q, dan sangat berkesan untuk besar r. Iaitu, ia berjalan dalam masa polinomial dalam log N apabila r adalah mengikut susunan log p. Kami ambil perhatian bahawa untuk kecil r, contohnya N =pq, p2q, ia ialah algoritma masa eksponen dalam log N. Dalam kertas kerja ini, kami mencadangkan kaedah untuk mempercepatkan LFM dari sudut pandangan praktikal. Selain itu, pertimbangan teori dan keputusan eksperimen disediakan yang menunjukkan bahawa algoritma yang dicadangkan menawarkan masa berjalan yang lebih pendek daripada LFM asal.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Shigenori UCHIYAMA, Naoki KANAYAMA, "Speeding up the Lattice Factoring Method" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 1, pp. 146-150, January 2001, doi: .
Abstract: 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 = pr 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 log p. We note that for small r, e.g. N =pq, p2q, 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_1_146/_p
Salinan
@ARTICLE{e84-a_1_146,
author={Shigenori UCHIYAMA, Naoki KANAYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Speeding up the Lattice Factoring Method},
year={2001},
volume={E84-A},
number={1},
pages={146-150},
abstract={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 = pr 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 log p. We note that for small r, e.g. N =pq, p2q, 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.},
keywords={},
doi={},
ISSN={},
month={January},}
Salinan
TY - JOUR
TI - Speeding up the Lattice Factoring Method
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 146
EP - 150
AU - Shigenori UCHIYAMA
AU - Naoki KANAYAMA
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2001
AB - 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 = pr 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 log p. We note that for small r, e.g. N =pq, p2q, 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.
ER -