The Implicit Factorization Problem was first introduced by May and Ritzenhofen at PKC'09. This problem aims to factorize two RSA moduli $N_1=p_1q_1$ and $N_2=p_2q_2$ when their prime factors share a certain number of least significant bits (LSBs). They proposed a lattice-based algorithm to tackle this problem and extended it to cover $k>2$ RSA moduli. Since then, several variations of the Implicit Factorization Problem have been studied, including the cases where $p_1$ and $p_2$ share some most significant bits (MSBs), middle bits, or both MSBs and LSBs at the same position. In this paper, we explore a more general case of the Implicit Factorization Problem, where the shared bits are located at different and unknown positions for different primes. We propose a lattice-based algorithm and analyze its efficiency under certain conditions. We also present experimental results to support our analysis.
翻译:隐式因子分解问题最初由May和Ritzenhofen于PKC'09中提出。该问题旨在因子分解两个RSA模数 $N_1 = p_1q_1$ 和 $N_2 = p_2q_2$ 当它们的质数因子共享某些最低有效位(LSB)时。他们提出了一个基于格的算法来解决该问题,并将其扩展到覆盖$k>2$个RSA模数。此后,已研究了隐式因子分解问题的几种变体,包括$p_1$和$p_2$共享某些最高有效位(MSB)、中间位或MSB和LSB在同一位置的情况。在本文中,我们探讨了隐式因子分解问题的一个更一般的情况,即用于不同质数的共享位位于不同且未知的位置。我们提出了一个基于格的算法,并分析了它在某些条件下的效率。我们还提供实验证据来支持我们的分析。