Advances in Mathematics of Communications (AMC)

Further results on implicit factoring in polynomial time

Pages: 205 - 217, Volume 3, Issue 2, May 2009      doi:10.3934/amc.2009.3.205

 Abstract        Full Text (235.3K)       Related Articles

Santanu Sarkar - Indian Statistical Institute, 203 B T Road, Kolkata 700 108, India (email)
Subhamoy Maitra - Indian Statistical Institute, 203 B T Road,, Kolkata 700 108, India (email)

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α, 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.

Keywords:  Implicit information, prime factorization.
Mathematics Subject Classification:  Primary: 11Y05; Secondary: 94A60.

Received: March 2009;      Revised: April 2009;      Available Online: May 2009.