[HGI-News-de] HGI Seminar Do. 13.11.: "Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits." von M. Herrmann

[Newsletter des Horst Görtz Instituts]

Hallo,

im Rahmen des HGI-Seminars "Aktuelle Themen der IT-Sicherheit" wird
am kommenden Donnerstag der folgende Vortrag angeboten:

Mathias Herrmann:
*Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits.*


Termin:
Donnerstag, der 13. November um  11.00 Uhr (*s.t.*)
Raum: IC 4/161

Interessierte sind herzlich eingeladen!


==============================================================
Abstract:

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 = O(log log N) blocks.
==============================================================

Informationen über die nächsten geplannten Vorträge im Rahmen des
HGI-Seminars sind auch im Web zu finden:
http://www.hgi.rub.de/hgi/hgi-seminar/aktuelles

Gruß,
Mathias Herrmann