Improved bounds for the implicit factorization problem

We study the problem of integer factoring with implicit hints. This problem is described as follows: Let N1 = p1q1,...,Nk = pkqk be k different RSA moduli of same bit-size, where q1,...qk are of the same bit-size too. Given the implicit information that p1,....pk share some certain portions of bit pattern, under what condition is it possible to factorize N1,...,Nk efficiently? This problem has been studied in many references recently and many interesting results have been obtained. In this paper, we modify the previousalgorithm presented by Sarkar and Maitra (IEEE TIT 57(6): 4002-4013, 2011). We show that our result achieves an improved generalized bounds in the cases where p1,...,pk share some amount of 1) most significant bits (MSBs); 2) least signi_cant bits (LSBs); 3) MSBs and LSBs together. As far as we are aware, our result is better than all known results. © 2013 AIMS.