The Number Field Sieve Factoring Algorithm

Abstract

Integer factorization has been interesting problem for mathematicians since centuries. Integer factorisation lies in the heart of Number Theory. There has been many algorithms for factorisation such as Dixon’s factorisation, continued fractions and Quadratic Sieve Factoring Algorithm. Many of the encryption algorithms in cryptog- raphy are based on the “hardness” in factoring large composite numbers with no small prime factors Number Field Sieve is the best known factoring algorithm. It works best with large numbers, for small one Quadratic Sieve is the best algorithm because of its low requirement of storage. Time complexity of GNFS (General Number Field q ](explanation of L-notation is given in appendix) and Sieving) algorithm is L n [ 13 , 3 643 that of quadratic sieve algorithm is L n [ 12 , 1].