Factoring a multiprime modulus N with random bits
Routo Terada, Reynaldo Cáceres Villena · 2015
In 2009, Heninger and Shacham presented an algorithm using the Hensel's lemma for reconstructing the prime factors of the modulus $$N = r_1r_2$$. This algorithm computes the prime factors of N in polynomial time, with high probability, assuming that a fraction greater than or equal to 59i¾ź% random bits of its primes $$r_1$$ and $$r_2$$ is given. In this paper, we present the analysis of Hensel's lemma for a multiprime modulus $$N = \prod ^u_{i=1}r_i$$ for $$u\ge 2$$ and we generalise the Heninger and Shacham's algorithm to determine the minimum fraction of random bits of its prime factors that is sufficient to factor N in polynomial time with high probability.