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