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 e cient 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.
|
