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:
The topic of this talk is the problem of computing the prime factorizati
on
of natural numbers. In practice, a large variety of probabilistic a
nd heuristic methods
is used for this task. However, none of these alg
orithms is ecient and the problem
itself is assumed to be computation
ally hard. The diffculty of factoring large integers
is fundamental fo
r the security of several cryptographical systems, one of which is the
public-key scheme RSA.
A more theoretical aspect of the integer facto
rization problem concerns deterministic
algorithms and the rigorous an
alysis of their runtime complexity. In 1977, Volker Strassen
presented
such a method based on fast polynomial arithmetic techniques. The procedur
e
computes the prime factorization of any natural number N in time eO(
N1=4), which has
been state of the art for the last forty years. In th
is talk, we discuss the core ideas
for improving the bound by a superp
olynomial factor.