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 formats: PDF | BibTeX Citation

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

Discussion forum: Show discussion | Start new discussion