**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

**Version: **20130510:054437 (All versions of this report)

**Short URL: **ia.cr/2013/249

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]