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.