American Institute of Mathematical Sciences

August  2013, 7(3): 243-251. doi: 10.3934/amc.2013.7.243

Improved bounds for the implicit factorization problem

 1 State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China, China, China

Received  November 2011 Revised  April 2013 Published  July 2013

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.
Citation: Yao Lu, Rui Zhang, Dongdai Lin. Improved bounds for the implicit factorization problem. Advances in Mathematics of Communications, 2013, 7 (3) : 243-251. doi: 10.3934/amc.2013.7.243
References:
 [1] H. Cohn and N. Heninger, Approximate common divisors via lattices, preprint, arXiv:1108.2714 [2] D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260. doi: 10.1007/s001459900030. [3] 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. [4] 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. [5] N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, in "Crytography and Coding,'' Springer, Berlin, (1997), 131-142. doi: 10.1007/BFb0024458. [6] 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. [7] A. May, "New RSA Vulnerabilities Using Lattice Reduction Methods,'' Ph.D thesis, University of Paderborn, 2003. [8] 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. [9] 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. [10] 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.

show all references

References:
 [1] H. Cohn and N. Heninger, Approximate common divisors via lattices, preprint, arXiv:1108.2714 [2] D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260. doi: 10.1007/s001459900030. [3] 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. [4] 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. [5] N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, in "Crytography and Coding,'' Springer, Berlin, (1997), 131-142. doi: 10.1007/BFb0024458. [6] 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. [7] A. May, "New RSA Vulnerabilities Using Lattice Reduction Methods,'' Ph.D thesis, University of Paderborn, 2003. [8] 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. [9] 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. [10] 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.
 [1] Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557 [2] Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems and Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 [3] Armin Lechleiter. The factorization method is independent of transmission eigenvalues. Inverse Problems and Imaging, 2009, 3 (1) : 123-138. doi: 10.3934/ipi.2009.3.123 [4] Jun Guo, Qinghua Wu, Guozheng Yan. The factorization method for cracks in elastic scattering. Inverse Problems and Imaging, 2018, 12 (2) : 349-371. doi: 10.3934/ipi.2018016 [5] Jayadev S. Athreya, Gregory A. Margulis. Values of random polynomials at integer points. Journal of Modern Dynamics, 2018, 12: 9-16. doi: 10.3934/jmd.2018002 [6] Laurent Imbert, Michael J. Jacobson, Jr.. Empirical optimization of divisor arithmetic on hyperelliptic curves over $\mathbb{F}_{2^m}$. Advances in Mathematics of Communications, 2013, 7 (4) : 485-502. doi: 10.3934/amc.2013.7.485 [7] Meina Gao. Small-divisor equation with large-variable coefficient and periodic solutions of DNLS equations. Discrete and Continuous Dynamical Systems, 2015, 35 (1) : 173-204. doi: 10.3934/dcds.2015.35.173 [8] Raluca Felea, Venkateswaran P. Krishnan, Clifford J. Nolan, Eric Todd Quinto. Common midpoint versus common offset acquisition geometry in seismic imaging. Inverse Problems and Imaging, 2016, 10 (1) : 87-102. doi: 10.3934/ipi.2016.10.87 [9] David Iglesias-Ponte, Juan Carlos Marrero, David Martín de Diego, Edith Padrón. Discrete dynamics in implicit form. Discrete and Continuous Dynamical Systems, 2013, 33 (3) : 1117-1135. doi: 10.3934/dcds.2013.33.1117 [10] Laura DeMarco, Holly Krieger, Hexi Ye. Common preperiodic points for quadratic polynomials. Journal of Modern Dynamics, 2022, 18: 363-413. doi: 10.3934/jmd.2022012 [11] Yosra Boukari, Houssem Haddar. The factorization method applied to cracks with impedance boundary conditions. Inverse Problems and Imaging, 2013, 7 (4) : 1123-1138. doi: 10.3934/ipi.2013.7.1123 [12] Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems and Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025 [13] Qinghua Wu, Guozheng Yan. The factorization method for a partially coated cavity in inverse scattering. Inverse Problems and Imaging, 2016, 10 (1) : 263-279. doi: 10.3934/ipi.2016.10.263 [14] Xiaodong Liu. The factorization method for scatterers with different physical properties. Discrete and Continuous Dynamical Systems - S, 2015, 8 (3) : 563-577. doi: 10.3934/dcdss.2015.8.563 [15] Lianwen Wang. Approximate controllability and approximate null controllability of semilinear systems. Communications on Pure and Applied Analysis, 2006, 5 (4) : 953-962. doi: 10.3934/cpaa.2006.5.953 [16] Dan Tiba. Implicit parametrizations and applications in optimization and control. Mathematical Control and Related Fields, 2020, 10 (3) : 455-470. doi: 10.3934/mcrf.2020006 [17] Nikolaos S. Papageorgiou, Vicenţiu D. Rădulescu, Dušan D. Repovš. Periodic solutions for implicit evolution inclusions. Evolution Equations and Control Theory, 2019, 8 (3) : 621-631. doi: 10.3934/eect.2019029 [18] Chaabane Djamal, Pirlot Marc. A method for optimizing over the integer efficient set. Journal of Industrial and Management Optimization, 2010, 6 (4) : 811-823. doi: 10.3934/jimo.2010.6.811 [19] Luigi Ambrosio, Gianluca Crippa, Philippe G. Lefloch. Leaf superposition property for integer rectifiable currents. Networks and Heterogeneous Media, 2008, 3 (1) : 85-95. doi: 10.3934/nhm.2008.3.85 [20] Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

2021 Impact Factor: 1.015