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 bitsize 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 bitsize 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 bitsize 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 latticebased 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)
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 Implicit InformationPrime Factorization.
 Contact author(s)
 subho @ isical ac in
 History
 20090330: last of 3 revisions
 20090311: received
 See all versions
 Short URL
 https://ia.cr/2009/108
 License

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} }