BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//jEvents 2.0 for Joomla//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VEVENT
UID:a4adc8e154ba59e14ee5d610b540c9fd
CATEGORIES:Lectures & Presentations
CREATED:20190305T170036
SUMMARY:Guest Talk: A babystep-giantstep method for faster deterministic integer factorization
LOCATION:SBA Research\, Vienna
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:\n\nThe topic of this talk is the problem of computing the prime factorizat
ion\nof natural numbers. In practice, a large variety of probabilistic and
heuristic methods\nis used for this task. However, none of these algorithms
is ecient and the problem\nitself is assumed to be computationally hard.
The diffculty of factoring large integers\nis fundamental for the security
of several cryptographical systems, one of which is the\npublic-key scheme
RSA.\nA more theoretical aspect of the integer factorization problem concer
ns deterministic\nalgorithms and the rigorous analysis of their runtime com
plexity. In 1977, Volker Strassen\npresented such a method based on fast po
lynomial arithmetic techniques. The procedure\ncomputes the prime factoriza
tion of any natural number N in time eO(N1=4), which has\nbeen state of the
art for the last forty years. In this talk, we discuss the core ideas\nfor
improving the bound by a superpolynomial factor. \n
CONTACT:Bettina Bauer
X-EXTRAINFO:02/10
DTSTAMP:20220817T115048Z
DTSTART:20180917T083000Z
DTEND:20180917T093000Z
SEQUENCE:0
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR