International Association
for Cryptologic Research

We propose a new algorithm to solve the Implicit Factorization Problem, which was introduced by May and Ritzenhofen at PKC\'09. In 2011, Sarkar and Maitra (IEEE TIT 57(6): 4002-4013, 2011) improved May and Ritzenhofen\'s results by making use of the technique for solving multivariate approximate common divisors problem. In this paper, based on the observation that the desired root of the equations that derived by Sarkar and Maitra contains large prime factors, which are already determined by some known integers, we develop new techniques to acquire better bounds. We show that our attack is the best among all known attacks, and give experimental results to verify the correctness. Additionally, for the first time, we can experimentally handle the implicit factorization for the case of balanced RSA moduli.