Factorisation and Elliptic Curves

Abstract:

Integer factorisation is one of the most important problems in number theory and computer science. In 1985, Lenstra proposed a factorisation algorithm using elliptic curves, which is currently the fastest known algorithm for finding 'small' prime factors. In this talk we will give an introduction to the factorisation problem and the theory of elliptic curves, as well as an overview of Lenstra's algorithm including an analysis of its complexity.