eprint.iacr.org will be offline for approximately an hour
for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between
April 12 and April 14, and some authors have been notified that they need to resubmit their papers.
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)
-
PDF
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- factoringGaussian reduction algorithmlattice
- Contact author(s)
- kurosawa @ mx ibaraki ac jp
- History
- 2013-05-10: last of 2 revisions
- 2013-05-03: 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}
}
