Paper 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.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 factoringGaussian reduction algorithmlattice
 Contact author(s)
 kurosawa @ mx ibaraki ac jp
 History
 20130510: last of 2 revisions
 20130503: received
 See all versions
 Short URL
 https://ia.cr/2013/249
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/249, author = {Kaoru Kurosawa and Takuma Ueda}, title = {How to Factor N_1 and N_2 When p_1=p_2 mod 2^t}, howpublished = {Cryptology ePrint Archive, Paper 2013/249}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/249}}, url = {https://eprint.iacr.org/2013/249} }