Paper 2009/108

Further Results on Implicit Factoring in Polynomial Time

Santanu Sarkar and Subhamoy Maitra

Abstract

In PKC 2009, May and Ritzenhofen presented interesting problems related to factoring large integers with some implicit hints. One of the problems is as follows. Consider $N_1 = p_1 q_1$ and $N_2 = p_2 q_2$, where $p_1, p_2, q_1, q_2$ are large primes. The primes $p_1, p_2$ are of same bit-size with the constraint that certain amount of Least Significant Bits (LSBs) of $p_1, p_2$ are same. Further the primes $q_1, q_2$ are of same bit-size without any constraint. May and Ritzenhofen proposed a strategy to factorize both $N_1, N_2$ in poly$(\log N)$ time ($N$ is an integer with same bit-size as $N_1, N_2$) with the implicit information that $p_1, p_2$ share certain amount of LSBs. We explore the same problem with a different lattice-based strategy. In a general framework, our method works when implicit information is available related to Least Significant as well as Most Significant Bits (MSBs). Given $q_1, q_2 \approx N^{\alpha}$, we show that one can factor $N_1, N_2$ simultaneously in poly$(\log N)$ time (under some assumption related to Gröbner Basis) when $p_1, p_2$ share certain amount of MSBs and/or LSBs. We also study the case when $p_1, p_2$ share some bits in the middle. Our strategy presents new and encouraging results in this direction. Moreover, some of the observations by May and Ritzenhofen get improved when we apply our ideas for the LSB case.

Note: Substantial Revision

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Implicit InformationPrime Factorization.
Contact author(s)
subho @ isical ac in
History
2009-03-30: last of 3 revisions
2009-03-11: received
See all versions
Short URL
https://ia.cr/2009/108
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/108,
      author = {Santanu Sarkar and Subhamoy Maitra},
      title = {Further Results on Implicit Factoring in Polynomial Time},
      howpublished = {Cryptology ePrint Archive, Paper 2009/108},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/108}},
      url = {https://eprint.iacr.org/2009/108}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.