Welcome to the resource topic for 2009/108
Title:
Further Results on Implicit Factoring in Polynomial Time
Authors: Santanu Sarkar, 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.
ePrint: https://eprint.iacr.org/2009/108
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .