Author Country (or Countries)



The security of many public-key cryptosystems, such as RSA, is based on the difficulty of factoring a composite integer. Until now, there is no known polynomial time algorithm to factor any composite integer with classical computers. In this paper, we study factoring n when n= pq is a product of two primes p and q satisfying that p≡lk1 mod 2q1 and q≡lk2 mod 2q2 for some positive integers q1,q2, k1, k2 ≤ logn and l.We show that n can be factored in time polynomial in logn if l < 2q and either | p−lk1 2q1 || q−lk2 2q2 |< lk or 2q ′ ≥ n1/4, where q = min{q1,q2}, q ′ = max{q1,q2} and k = min{k1, k2}. We also show that the result of Steinfeld and Zheng [21] when the two primes p and q share least significant bits is a special case of our results. Our results point out the warring for cryptographic designers to be careful when generating primes for the RSA modulus

Suggested Reviewers


Digital Object Identifier (DOI)