Generalized Implicit Factorization Problem

The Implicit Factorization Problem (IFP) was first introduced by May and Ritzenhofen at PKC’09, which concerns the factorization of two RSA moduli \(N_1=p_1q_1\) and \(N_2=p_2q_2\) , where \(p_1\) and \(p_2\) share a certain consecutive number of least significant bits. Since its introduction, many different variants of IFP have been considered, such as the cases where \(p_1\) and \(p_2\) share most significant bits or middle bits at the same positions. In this paper, we consider a more generalized case of IFP, in which the shared consecutive bits can be located at any positions in each prime, not necessarily required to be located at the same positions as before. We propose a lattice-based algorithm to solve this problem under specific conditions, and also provide some experimental results to verify our analysis.