Paper 2007/374

On Factoring Arbitrary Integers with Known Bits

Mathias Herrmann and Alexander May

Abstract

We study the {\em factoring with known bits problem}, where we are given a composite integer N=p1p2pr 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 given bits, where denotes the harmonic number.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Full Version of the Workshop "Kryptologie in Theorie und Praxis" paper
Keywords
factoring
Contact author(s)
herrmann @ rbg informatik tu-darmstadt de
History
2007-09-19: received
Short URL
https://ia.cr/2007/374
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/374,
      author = {Mathias Herrmann and Alexander May},
      title = {On Factoring Arbitrary Integers with Known Bits},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/374},
      year = {2007},
      url = {https://eprint.iacr.org/2007/374}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.