May  2009, 3(2): 205-217. doi: 10.3934/amc.2009.3.205

Further results on implicit factoring in polynomial time


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


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

Received  March 2009 Revised  April 2009 Published  May 2009

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α, 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.
Citation: Santanu Sarkar, Subhamoy Maitra. Further results on implicit factoring in polynomial time. Advances in Mathematics of Communications, 2009, 3 (2) : 205-217. doi: 10.3934/amc.2009.3.205

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


G.F. Webb. The prime number periodical cicada problem. Discrete & Continuous Dynamical Systems - B, 2001, 1 (3) : 387-399. doi: 10.3934/dcdsb.2001.1.387


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


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


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


Jon Chaika, Bryna Kra. A prime system with many self-joinings. Journal of Modern Dynamics, 2021, 17: 213-265. doi: 10.3934/jmd.2021007


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


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


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


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


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


Taylor McAdam. Almost-prime times in horospherical flows on the space of lattices. Journal of Modern Dynamics, 2019, 15: 277-327. doi: 10.3934/jmd.2019022


Kaushik Nath, Palash Sarkar. Efficient arithmetic in (pseudo-)Mersenne prime order fields. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020113


Alex H. Ardila. Stability of ground states for logarithmic Schrödinger equation with a $δ^{\prime}$-interaction. Evolution Equations & Control Theory, 2017, 6 (2) : 155-175. doi: 10.3934/eect.2017009


Dan Tiba. Implicit parametrizations and applications in optimization and control. Mathematical Control & Related Fields, 2020, 10 (3) : 455-470. doi: 10.3934/mcrf.2020006


Nikolaos S. Papageorgiou, Vicenţiu D. Rădulescu, Dušan D. Repovš. Periodic solutions for implicit evolution inclusions. Evolution Equations & Control Theory, 2019, 8 (3) : 621-631. doi: 10.3934/eect.2019029


Rui Wang, Denghua Zhong, Yuankun Zhang, Jia Yu, Mingchao Li. A multidimensional information model for managing construction information. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1285-1300. doi: 10.3934/jimo.2015.11.1285


Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017


Subrata Dasgupta. Disentangling data, information and knowledge. Big Data & Information Analytics, 2016, 1 (4) : 377-389. doi: 10.3934/bdia.2016016


Apostolis Pavlou. Asymmetric information in a bilateral monopoly. Journal of Dynamics & Games, 2016, 3 (2) : 169-189. doi: 10.3934/jdg.2016009

2020 Impact Factor: 0.935


  • PDF downloads (83)
  • HTML views (0)
  • Cited by (10)

Other articles
by authors

[Back to Top]