Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits
verfasst von : Mathias Herrmann, Alexander May
Erschienen in: Advances in Cryptology - ASIACRYPT 2008
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the problem of finding solutions to linear equations modulo an unknown divisor
p
of a known composite integer
N
. An important application of this problem is factorization of
N
with given bits of
p
. It is well-known that this problem is polynomial-time solvable if at most half of the bits of
p
are unknown and if the unknown bits are located in one
consecutive
block. We introduce an heuristic algorithm that extends
factoring with known bits
to an arbitrary number
n
of blocks. Surprisingly, we are able to show that ln (2) ≈ 70% of the bits are sufficient for any
n
in order to find the factorization. The algorithm’s running time is however exponential in the parameter
n
. Thus, our algorithm is polynomial time only for
$n = {\mathcal O}(\log\log N)$
blocks.