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
2007


Editors

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


Copyright © Gesellschaft für Informatik, Bonn

Contents

On factoring arbitrary integers with known bits

M. Herrmann and A. May

Abstract


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