**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{\"o}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.

**Category / Keywords: **foundations / Implicit Information, Prime Factorization.

**Date: **received 6 Mar 2009, last revised 30 Mar 2009

**Contact author: **subho at isical ac in

**Available format(s): **PDF | BibTeX Citation

**Note: **Substantial Revision

**Version: **20090330:105511 (All versions of this report)

**Short URL: **ia.cr/2009/108

[ Cryptology ePrint archive ]