Advanced Search
Article Contents
Article Contents

Improved bounds for the implicit factorization problem

Abstract Related Papers Cited by
  • We study the problem of integer factoring with implicit hints. This problem is described as follows: Let $N_{1}=p_{1}q_{1},\dots,N_{k}=p_{k}q_{k}$ be $k$ different RSA moduli of same bit-size, where $q_1,\dots,q_k$ are of the same bit-size too. Given the implicit information that $p_{1},\dots,p_{k}$ share some certain portions of bit pattern, under what condition is it possible to factorize $N_{1},\dots,N_{k}$ efficiently? This problem has been studied in many references recently and many interesting results have been obtained. In this paper, we modify the previous algorithm presented by Sarkar and Maitra (IEEE TIT 57(6): 4002-4013, 2011). We show that our result achieves an improved generalized bounds in the cases where $p_{1},\dots,p_{k}$ share some amount of 1) most significant bits (MSBs); 2) least significant bits (LSBs); 3) MSBs and LSBs together. As far as we are aware, our result is better than all known results.
    Mathematics Subject Classification: Primary: 11Y05; Secondary: 94A60.


    \begin{equation} \\ \end{equation}
  • [1]

    H. Cohn and N. HeningerApproximate common divisors via lattices, preprint, arXiv:1108.2714


    D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260.doi: 10.1007/s001459900030.


    J. C. Faugère, R. Marinier and G. Renault, Implicit factoring with shared most significant and middle bits, in "Public Key Cryptography-PKC 2010,'' (2010), 70-87.doi: 10.1007/978-3-642-13013-7_5.


    M. Herrmann and A. May, Solving linear equations modulo divisors: On factoring given any bits in "Advances in Cryptology-ASIACRYPT 2008,'' (2008), 406-424.doi: 10.1007/978-3-540-89255-7_25.


    N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, in "Crytography and Coding,'' Springer, Berlin, (1997), 131-142.doi: 10.1007/BFb0024458.


    A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Math. Annalen, 261 (1982), 515-534.doi: 10.1007/BF01457454.


    A. May, "New RSA Vulnerabilities Using Lattice Reduction Methods,'' Ph.D thesis, University of Paderborn, 2003.


    A. May and M. Ritzenhofen, Implicit factoring: On polynomial time factoring given only an implicit hint, in "Public Key Cryptography-PKC 2009,'' (2009), 1-14.doi: 10.1007/978-3-642-00468-1_1.


    S. Sarkar and S. Maitra, Approximate integer common divisor problem relates to implicit factorization, IEEE Trans. Inform. Theory, 57 (2011), 4002-4013.doi: 10.1109/TIT.2011.2137270.


    S. Sarkar and S. Maitra, Further results on implicit factoring in polynomial time, Adv. Math. Commun., 3 (2009), 205-217.doi: 10.3934/amc.2009.3.205.

  • 加载中

Article Metrics

HTML views() PDF downloads(82) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint