The Number Field Sieve

This thesis project is focused on studying the number field sieve. The number field sieve is a factoring algorithm which uses algebraic number theory and is one of the fastest known factoring algorithms today. Factoring large integers into prime factors is an extremely difficult problem, yet also extremely important in cryptography. The security of the cryptosystem RSA is entirely based on the difficulty of factoring certain large integers into a product of two distinct large primes. While the number field sieve is one of the fastest factoring algorithms known, it is still not efficient enough to factor cryptographic sized integers.

In this thesis we will examine the algorithm of the number field sieve and discuss some important advancements. In particular, we will focus on the advancements that have been done in the polynomial selection step, the first main step of the number field sieve. The polynomial selected determines the number field by which computations are carried out in the remainder of the algorithm. Selection of a good polynomial allows for better time efficiency and a higher probability that the algorithm will be successful in factoring.