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, ().

[2]

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

[3]

J. C. Faugère, R. Marinier and G. Renault, Implicit factoring with shared most significant and middle bits,, in, (2010), 70. 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, (2008), 406. doi: 10.1007/978-3-540-89255-7_25.

[5]

N. Howgrave-Graham, Finding small roots of univariate modular equations revisited,, in, (1997), 131. 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. 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, (2009), 1. 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. 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. doi: 10.3934/amc.2009.3.205.

show all references

References:
[1]

H. Cohn and N. Heninger, Approximate common divisors via lattices,, preprint, ().

[2]

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

[3]

J. C. Faugère, R. Marinier and G. Renault, Implicit factoring with shared most significant and middle bits,, in, (2010), 70. 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, (2008), 406. doi: 10.1007/978-3-540-89255-7_25.

[5]

N. Howgrave-Graham, Finding small roots of univariate modular equations revisited,, in, (1997), 131. 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. 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, (2009), 1. 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. 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. doi: 10.3934/amc.2009.3.205.

[1]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[2]

Raluca Felea, Venkateswaran P. Krishnan, Clifford J. Nolan, Eric Todd Quinto. Common midpoint versus common offset acquisition geometry in seismic imaging. Inverse Problems & Imaging, 2016, 10 (1) : 87-102. doi: 10.3934/ipi.2016.10.87

[3]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[4]

Jun Guo, Qinghua Wu, Guozheng Yan. The factorization method for cracks in elastic scattering. Inverse Problems & Imaging, 2018, 12 (2) : 349-371. doi: 10.3934/ipi.2018016

[5]

Armin Lechleiter. The factorization method is independent of transmission eigenvalues. Inverse Problems & Imaging, 2009, 3 (1) : 123-138. doi: 10.3934/ipi.2009.3.123

[6]

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

[7]

David Iglesias-Ponte, Juan Carlos Marrero, David Martín de Diego, Edith Padrón. Discrete dynamics in implicit form. Discrete & Continuous Dynamical Systems - A, 2013, 33 (3) : 1117-1135. doi: 10.3934/dcds.2013.33.1117

[8]

Konstantinos Drakakis, Roderick Gow, Scott Rickard. Common distance vectors between Costas arrays. Advances in Mathematics of Communications, 2009, 3 (1) : 35-52. doi: 10.3934/amc.2009.3.35

[9]

Ryusuke Kon. Dynamics of competitive systems with a single common limiting factor. Mathematical Biosciences & Engineering, 2015, 12 (1) : 71-81. doi: 10.3934/mbe.2015.12.71

[10]

Alain Bensoussan, John Liu, Jiguang Yuan. Singular control and impulse control: A common approach. Discrete & Continuous Dynamical Systems - B, 2010, 13 (1) : 27-57. doi: 10.3934/dcdsb.2010.13.27

[11]

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

[12]

Meina Gao. Small-divisor equation with large-variable coefficient and periodic solutions of DNLS equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (1) : 173-204. doi: 10.3934/dcds.2015.35.173

[13]

Yosra Boukari, Houssem Haddar. The factorization method applied to cracks with impedance boundary conditions. Inverse Problems & Imaging, 2013, 7 (4) : 1123-1138. doi: 10.3934/ipi.2013.7.1123

[14]

Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems & Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025

[15]

Qinghua Wu, Guozheng Yan. The factorization method for a partially coated cavity in inverse scattering. Inverse Problems & Imaging, 2016, 10 (1) : 263-279. doi: 10.3934/ipi.2016.10.263

[16]

Xiaodong Liu. The factorization method for scatterers with different physical properties. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 563-577. doi: 10.3934/dcdss.2015.8.563

[17]

Lianwen Wang. Approximate controllability and approximate null controllability of semilinear systems. Communications on Pure & Applied Analysis, 2006, 5 (4) : 953-962. doi: 10.3934/cpaa.2006.5.953

[18]

Chaabane Djamal, Pirlot Marc. A method for optimizing over the integer efficient set. Journal of Industrial & 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 & 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 & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (3)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]