Logo des Repositoriums

Auflistung nach Autor:in "Herrmann, Mathias"

1 - 1 von 1
  • Konferenzbeitrag
    On Factoring Arbitrary Integers with Known Bits
    (Informatik 2007 – Informatik trifft Logistik – Band 2, 2007) Herrmann, Mathias; May, Alexander
    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.