On Factoring Arbitrary Integers with Known Bits

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.
  • Vollständige Referenz
  • BibTeX
Herrmann, M. & May, A., (2007). On Factoring Arbitrary Integers with Known Bits. In: Herzog, O., Rödiger, K.-H., Ronthaler, M. & Koschke, R. (Hrsg.), Informatik 2007 – Informatik trifft Logistik – Band 2. Bonn: Gesellschaft für Informatik e. V.. (S. 195-199).
@inproceedings{mci/Herrmann2007,
author = {Herrmann, Mathias AND May, Alexander},
title = {On Factoring Arbitrary Integers with Known Bits},
booktitle = {Informatik 2007 – Informatik trifft Logistik – Band 2},
year = {2007},
editor = {Herzog, Otthein AND Rödiger, Karl-Heinz AND Ronthaler, Marc AND Koschke, Rainer} ,
pages = { 195-199 },
publisher = {Gesellschaft für Informatik e. V.},
address = {Bonn}
}
DateienGroesseFormatAnzeige
195.pdf153.3Kb PDF Öffnen

Haben Sie fehlerhafte Angaben entdeckt? Sagen Sie uns Bescheid: Feedback abschicken

Mehr Information

ISBN: 978-3-88579-206-1
ISSN: 1617-5468
Datum: 2007
Sprache: en (en)
Typ: Text/Conference Paper
Sammlungen

Zur Langanzeige