How to Factor N 1 and N 2 When p 1 =p 2 mod 2 t .
Kaoru Kurosawa, Takuma Ueda · 2013
Abstract. Let N1 = p1q1 and N2 = p2q2 be two different RSA moduli. Suppose that p1 = p2 mod 2 t for some t, and q1 and q2 are bit primes. Then May and Ritzenhofen showed that N1 and N2 can be factored in quadratic time if t 2+ 3: In this paper, we improve this lower bound on t. Namely we prove that N1 and N2 can be factored in quadratic time if t 2+ 1: Further our simulation result shows that our bound is tight.