** Factoring large numbers: easy or hard
**
Herman J.J. te Riele
CWI Amsterdam

Abstract:

In Vol. 2: "Seminumerical algorithms" of Knuth's "The art of computer
programming"
(first edition appeared in 1969, third in 1997), a prominent place is
taken by algorithms
for factoring large numbers. In addition, the publication, in 1978, of
the RSA public-key
cryptographic system has stimulated renewed interest in factoring,
because the security
of RSA depends on the difficulty of factoring large numbers and because
the computational
complexity of factoring large numbers was (and still is) unknown. As a
result, the world
record for factoring large numbers has been pushed forward from about 40
digits in 1969
to 200 digits in 2005.
In this talk we will explain the main algorithmic developments behind
this progress and
try to answer the question asked in the title of this talk.

back to the list of talks