How to Factor N_1 and N_2 When p_1=p_2 mod 2^t

Kaoru Kurosawa; Takuma Ueda

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_{1} q_{1}$ and $N_{2} = p_{2} q_{2}$ be two different RSA moduli. Suppose that $p_{1} = p_{2} mod 2^{t}$ for some $t$ , and $q_{1}$ and $q_{2}$ are $α$ bit primes. Then May and Ritzenhofen showed that $N_{1}$ and $N_{2}$ can be factored in quadratic time if $t \geq 2 α + 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 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: factoring Gaussian reduction algorithm lattice
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},
      url = {https://eprint.iacr.org/2013/249}
}