Factoring numbers, which was once a mathematical problem without practical importance, is now recognized as a very significant problem: it is closely connected to the security of encrypted messages on the internet.

So how does one factor a number? If it is small, say 119, you might proceed by simply trying to divide by all the small primes in the hope of stumbling on a divisor. This method becomes hopelessly inefficient if you are trying to factor a larger number, such as 42680447189985041129249.

We will discuss several algorithms that allow one to factor large numbers quickly, culminating with the quadratic sieve which can factor numbers with as many as 100 digits.