Computational Algebra Seminar

Computational Algebra Seminar

Camilla Gaardsted

Aarhus University

Prime Factorisation

Thursday 3rd October, 3:05-4pm

Carslaw 360

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 x2 = y2 (mod N).

    In my talk I will describe QS and NFS.