On Factoring Arbitrary Integers with Known Bits
Mathias Herrmann, Alexander May · 2007
Abstract: We study the factoring with known bits problem, where we are given a composite integer N = p1p2... pr and oracle access to the bits of the prime factors pi, i = 1,..., r. Our goal is to find the full factorization of N in polynomial time with a minimal number of calls to the oracle. We present a rigorous algorithm that efficiently factorsN given (1 − 1 r Hr) logN bits, whereHr denotes the r th harmonic number. 1