Welcome to the resource topic for
**2007/374**

**Title:**

On Factoring Arbitrary Integers with Known Bits

**Authors:**
Mathias Herrmann, Alexander May

**Abstract:**

We study the {\em factoring with known bits problem}, where we are given a composite integer N=p_1p_2\dots p_r and oracle access to the bits of the prime factors p_i, i=1, \dots, 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-\frac{1}{r}H_r)\log N bits, where H_r denotes the r^{th} harmonic number.

**ePrint:**
https://eprint.iacr.org/2007/374

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .