Konferenzbeitrag
On Factoring Arbitrary Integers with Known Bits
Lade...
Volltext URI
Dokumententyp
Text/Conference Paper
Dateien
Zusatzinformation
Datum
2007
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik e. V.
Zusammenfassung
We 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.