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)
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.