Gesellschaft für Informatik e.V.

Lecture Notes in Informatics

INFORMATIK 2007 Informatik trifft Logistik Band 2 Beiträge der 37. Jahrestagung der Gesellschaft für Informatik e.V. (GI) 24. - 27. September 2007 in Bremen P-110, 195-199 (2007).

Gesellschaft für Informatik, Bonn


Otthein Herzog (ed.), Karl-Heinz Rödiger (ed.), Marc Ronthaler (ed.), Rainer Koschke (ed.)

Copyright © Gesellschaft für Informatik, Bonn


On factoring arbitrary integers with known bits

M. Herrmann and A. May


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 factors N given (1 - 1 H r r) log N bits, where Hr denotes the rth harmonic number.

Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-206-1

Last changed 04.10.2013 18:14:58