||A Simple Improvement for Integer Factorizations with Implicit Hints
Harasawa, Ryuichi ,
Ryuto, HeiwaSueyoshi, Yutaka
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
1096 , 2016-06-01 , 電子情報通信学会
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.