My master thesis was about prime factorisation. Given an integer N, the task is to find the prime factors of N. Before 1970 it was hardly possible to factorise a random N consisting of more than 20 digits. Each decade since the 70's has had a dominating factorisation algorithm:

• The Continued Fraction Factorisation Algorithm in the 70's.
• The Quadratic Sieve (QS) in the 80's.
• The Number Field Sieve (NFS) in the 90's and today.

These algorithms have raised the number of digits of N to about 160 for a random N and more than 200 digits for special N. The three algorithms all build on the same principle, that is, to find non-trivial integer solutions x and y to the equation x² = y² (mod N).

In my talk I will describe QS and NFS.