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
Récemment, Boneh et al. a proposé un algorithme intéressant pour factoriser des entiers, appelé LFM (Lattice Factoring Method). Il est basé sur les techniques de Coppersmith et Howgrave-Graham, à savoir qu’il utilise intelligemment l’algorithme LLL. Le LFM concerne les entiers de la forme N = pr q, et est très efficace pour les grands r. Autrement dit, il s'exécute en temps polynomial dans le journal N quand r est dans l'ordre du journal p. On note que pour les petits r, par exemple N =pq, p2q, c'est un algorithme de temps exponentiel en log N. Dans cet article, nous proposons une méthode pour accélérer le LFM d’un point de vue pratique. En outre, des considérations théoriques et des résultats expérimentaux sont fournis qui montrent que l'algorithme proposé offre un temps d'exécution plus court que le LFM original.
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.
Copier
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
Copier
@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},}
Copier
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 -