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 .