On Factoring Arbitrary Integers with Known Bits
| dc.contributor.author | Herrmann, Mathias | |
| dc.contributor.author | May, Alexander | |
| dc.contributor.editor | Herzog, Otthein | |
| dc.contributor.editor | Rödiger, Karl-Heinz | |
| dc.contributor.editor | Ronthaler, Marc | |
| dc.contributor.editor | Koschke, Rainer | |
| dc.date.accessioned | 2019-05-15T09:04:54Z | |
| dc.date.available | 2019-05-15T09:04:54Z | |
| dc.date.issued | 2007 | |
| dc.description.abstract | 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. | en |
| dc.identifier.isbn | 978-3-88579-206-1 | |
| dc.identifier.pissn | 1617-5468 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/22479 | |
| dc.language.iso | en | |
| dc.publisher | Gesellschaft für Informatik e. V. | |
| dc.relation.ispartof | Informatik 2007 – Informatik trifft Logistik – Band 2 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Proceedings, Volume P-110 | |
| dc.title | On Factoring Arbitrary Integers with Known Bits | en |
| dc.type | Text/Conference Paper | |
| gi.citation.endPage | 199 | |
| gi.citation.publisherPlace | Bonn | |
| gi.citation.startPage | 195 | |
| gi.conference.date | 24.-27. September 2007 | |
| gi.conference.location | Bremen | |
| gi.conference.sessiontitle | Regular Research Papers |
Dateien
Originalbündel
1 - 1 von 1