Herrmann, MathiasMay, AlexanderHerzog, OttheinRödiger, Karl-HeinzRonthaler, MarcKoschke, Rainer2019-05-152019-05-152007978-3-88579-206-1https://dl.gi.de/handle/20.500.12116/22479We study the factoring with known bits problem, where we are given a composite integer N = p1 p2 . . . 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 factors N given (1 − 1/r Hr ) log N bits, where Hr denotes the rth harmonic number.enText/Conference Paper1617-5468