## Cryptology ePrint Archive: Report 2013/249

How to Factor N_1 and N_2 When p_1=p_2 mod 2^t

Kaoru Kurosawa and Takuma Ueda

Abstract: Let $N_1=p_1q_1$ and $N_2=p_2q_2$ be two different RSA moduli. Suppose that $p_1=p_2 \bmod 2^t$ for some $t$, and $q_1$ and $q_2$ are $\alpha$ bit primes. Then May and Ritzenhofen showed that $N_1$ and $N_2$ can be factored in quadratic time if $t \geq 2\alpha+3.$

In this paper, we improve this lower bound on $t$. Namely we prove that $N_1$ and $N_2$ can be factored in quadratic time if $t \geq 2\alpha+1.$ Further our simulation result shows that our bound is tight.

Category / Keywords: factoring, Gaussian reduction algorithm, lattice

Date: received 1 May 2013, last revised 9 May 2013

Contact author: kurosawa at mx ibaraki ac jp

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2013/249

[ Cryptology ePrint archive ]