The Number Field Sieve

We present two algorithms for splitting a general composite number, the quadratic sieve algorithm (QS) and the general number field sieve algorithm (NFS). The former is the method of choice for integers between 50 and 110 digits, and the latter beyond. They share a common strategy, but the NFS is far more sophisticated. We therefore present the QS as a preparation for the NFS. We also give two algorithms for the discrete logarithm problem in prime fields, the index-calculus method (ICM) and the number field sieve for the discrete logarithm problem (NFS-dlog). They have crossover point at 66-digit primes. The only limitation made was restricting to the prime field case. The NFS-dlog uses ideas from both the NFS and the ICM. We also study the algebraic background and estimate the running times of both the NFS and the NFS-dlog