# American Institute of Mathematical Sciences

November  2010, 4(4): 519-531. doi: 10.3934/amc.2010.4.519

## Some applications of lattice based root finding techniques

 1 Indian Statistical Institute, 203 B T Road, Kolkata 700 108, India 2 Indian Statistical Institute, 203 B T Road,, Kolkata 700 108

Received  December 2009 Revised  August 2010 Published  November 2010

In this paper we present some problems and their solutions exploiting lattice based root finding techniques.
In CaLC 2001, Howgrave-Graham proposed a method to find the Greatest Common Divisor (GCD) of two large integers when one of the integers is exactly known and the other one is known approximately. In this paper, we present three applications of the technique. The first one is to show deterministic polynomial time equivalence between factoring $N$ ($N = pq$, where $p > q$ or $p, q$ are of same bit size) and knowledge of $q$-1 mod $p$. Next, we consider the problem of finding smooth integers in a short interval. The third one is to factorize $N$ given a multiple of the decryption exponent in RSA.
In Asiacrypt 2006, Jochemsz and May presented a general strategy for finding roots of a polynomial. We apply that technique to solve the following two problems. The first one is to factorize $N$ given an approximation of a multiple of the decryption exponent in RSA. The second one is to solve the implicit factorization problem given three RSA moduli considering certain portions of LSBs as well as MSBs of one set of three secret primes are same.
Citation: Santanu Sarkar, Subhamoy Maitra. Some applications of lattice based root finding techniques. Advances in Mathematics of Communications, 2010, 4 (4) : 519-531. doi: 10.3934/amc.2010.4.519
##### References:

show all references

##### References:
 [1] 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 [2] Michele Barbi, Angelo Di Garbo, Rita Balocchi. Improved integrate-and-fire model for RSA. Mathematical Biosciences & Engineering, 2007, 4 (4) : 609-615. doi: 10.3934/mbe.2007.4.609 [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] 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 [5] 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 [6] 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 [7] 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 [8] 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 [9] 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 [10] Shixiong Wang, Longjiang Qu, Chao Li, Shaojing Fu, Hao Chen. Finding small solutions of the equation $\mathit{{Bx-Ay = z}}$ and its applications to cryptanalysis of the RSA cryptosystem. Advances in Mathematics of Communications, 2021, 15 (3) : 441-469. doi: 10.3934/amc.2020076 [11] Andreas Kirsch, Albert Ruiz. The Factorization Method for an inverse fluid-solid interaction scattering problem. Inverse Problems & Imaging, 2012, 6 (4) : 681-695. doi: 10.3934/ipi.2012.6.681 [12] Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su. Parallel matrix factorization for low-rank tensor completion. Inverse Problems & Imaging, 2015, 9 (2) : 601-624. doi: 10.3934/ipi.2015.9.601 [13] Dinh-Liem Nguyen. The factorization method for the Drude-Born-Fedorov model for periodic chiral structures. Inverse Problems & Imaging, 2016, 10 (2) : 519-547. doi: 10.3934/ipi.2016010 [14] Bastian Gebauer, Nuutti Hyvönen. Factorization method and inclusions of mixed type in an inverse elliptic boundary value problem. Inverse Problems & Imaging, 2008, 2 (3) : 355-372. doi: 10.3934/ipi.2008.2.355 [15] Anahita Eslami Rad, Enrique G. Reyes. The Kadomtsev-Petviashvili hierarchy and the Mulase factorization of formal Lie groups. Journal of Geometric Mechanics, 2013, 5 (3) : 345-364. doi: 10.3934/jgm.2013.5.345 [16] Lorenzo Audibert. The Generalized Linear Sampling and factorization methods only depends on the sign of contrast on the boundary. Inverse Problems & Imaging, 2017, 11 (6) : 1107-1119. doi: 10.3934/ipi.2017051 [17] Sangye Lungten, Wil H. A. Schilders, Joseph M. L. Maubach. Sparse inverse incidence matrices for Schilders' factorization applied to resistor network modeling. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 227-239. doi: 10.3934/naco.2014.4.227 [18] Sujit Kumar Samanta, Rakesh Nandi. Analysis of $GI^{[X]}/D$-$MSP/1/\infty$ queue using $RG$-factorization. Journal of Industrial & Management Optimization, 2021, 17 (2) : 549-573. doi: 10.3934/jimo.2019123 [19] Houssem Haddar, Alexander Konschin. Factorization method for imaging a local perturbation in inhomogeneous periodic layers from far field measurements. Inverse Problems & Imaging, 2020, 14 (1) : 133-152. doi: 10.3934/ipi.2019067 [20] Nuutti Hyvönen, Harri Hakula, Sampsa Pursiainen. Numerical implementation of the factorization method within the complete electrode model of electrical impedance tomography. Inverse Problems & Imaging, 2007, 1 (2) : 299-317. doi: 10.3934/ipi.2007.1.299

2020 Impact Factor: 0.935