IEICE TRANSACTIONS on Fundamentals
A Simple Improvement for Integer Factorizations with Implicit Hints
Summary :
In this paper, we describe an improvement of integer factorization of k RSA moduli Ni=piqi (1≤i≤k) with implicit hints, namely all pi share their t least significant bits. May et al. reduced this problem to finding a shortest (or a relatively short) vector in the lattice of dimension k obtained from a given system of k RSA moduli, for which they applied Gaussian reduction or the LLL algorithm. In this paper, we improve their method by increasing the determinant of the lattice obtained from the k RSA moduli. We see that, after our improvement, May et al.'s method works smoothly with higher probability. We further verify the efficiency of our method by computer experiments for various parameters.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.6 pp.1090-1096
- Publication Date
- 2016/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E99.A.1090
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Ryuichi HARASAWA
Nagasaki University
Heiwa RYUTO
Nagasaki University
Yutaka SUEYOSHI
Nagasaki University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Ryuichi HARASAWA, Heiwa RYUTO, Yutaka SUEYOSHI, "A Simple Improvement for Integer Factorizations with Implicit Hints" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 6, pp. 1090-1096, June 2016, doi: 10.1587/transfun.E99.A.1090.
Abstract: In this paper, we describe an improvement of integer factorization of k RSA moduli Ni=piqi (1≤i≤k) with implicit hints, namely all pi share their t least significant bits. May et al. reduced this problem to finding a shortest (or a relatively short) vector in the lattice of dimension k obtained from a given system of k RSA moduli, for which they applied Gaussian reduction or the LLL algorithm. In this paper, we improve their method by increasing the determinant of the lattice obtained from the k RSA moduli. We see that, after our improvement, May et al.'s method works smoothly with higher probability. We further verify the efficiency of our method by computer experiments for various parameters.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.1090/_p
Copy
@ARTICLE{e99-a_6_1090,
author={Ryuichi HARASAWA, Heiwa RYUTO, Yutaka SUEYOSHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Simple Improvement for Integer Factorizations with Implicit Hints},
year={2016},
volume={E99-A},
number={6},
pages={1090-1096},
abstract={In this paper, we describe an improvement of integer factorization of k RSA moduli Ni=piqi (1≤i≤k) with implicit hints, namely all pi share their t least significant bits. May et al. reduced this problem to finding a shortest (or a relatively short) vector in the lattice of dimension k obtained from a given system of k RSA moduli, for which they applied Gaussian reduction or the LLL algorithm. In this paper, we improve their method by increasing the determinant of the lattice obtained from the k RSA moduli. We see that, after our improvement, May et al.'s method works smoothly with higher probability. We further verify the efficiency of our method by computer experiments for various parameters.},
keywords={},
doi={10.1587/transfun.E99.A.1090},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - A Simple Improvement for Integer Factorizations with Implicit Hints
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1090
EP - 1096
AU - Ryuichi HARASAWA
AU - Heiwa RYUTO
AU - Yutaka SUEYOSHI
PY - 2016
DO - 10.1587/transfun.E99.A.1090
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2016
AB - In this paper, we describe an improvement of integer factorization of k RSA moduli Ni=piqi (1≤i≤k) with implicit hints, namely all pi share their t least significant bits. May et al. reduced this problem to finding a shortest (or a relatively short) vector in the lattice of dimension k obtained from a given system of k RSA moduli, for which they applied Gaussian reduction or the LLL algorithm. In this paper, we improve their method by increasing the determinant of the lattice obtained from the k RSA moduli. We see that, after our improvement, May et al.'s method works smoothly with higher probability. We further verify the efficiency of our method by computer experiments for various parameters.
ER -
English
