Previous month Previous day Next day Next month
By Year By Month By Week Today Search Jump to month

Guest Talk: A babystep-giantstep method for faster deterministic integer factorization

Download as iCal file
Monday, 17. September 2018, 10:30 - 11:30
Category: Lectures & Presentations | created by This email address is being protected from spambots. You need JavaScript enabled to view it.

The topic of this talk is the problem of computing the prime factorization
of natural numbers. In practice, a large variety of probabilistic and heuristic methods
is used for this task. However, none of these algorithms is ecient and the problem
itself is assumed to be computationally hard. The diffculty of factoring large integers
is fundamental for the security of several cryptographical systems, one of which is the
public-key scheme RSA.
A more theoretical aspect of the integer factorization problem concerns deterministic
algorithms and the rigorous analysis of their runtime complexity. In 1977, Volker Strassen
presented such a method based on fast polynomial arithmetic techniques. The procedure
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 this talk, we discuss the core ideas
for improving the bound by a superpolynomial factor. 

Location SBA Research, Vienna
Contact Bettina Bauer