You are looking at a specific version 20130510:054437 of this paper.
See the latest version.
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
- 2013-05-10: last of 2 revisions
- 2013-05-03: received
- See all versions
- Short URL
- https://ia.cr/2013/249
- License
-
CC BY