CentralNotice From Wikipedia, the free encyclopedia Jump to: navigation , search In number theory , the general number field sieve ( GNFS ) is the most efficient classical algorithm known for factoring integers larger than 100 digits. Heuristically , its complexity for factoring an integer n (consisting of bits) is of the form (in L-notation ), where ln is the natural logarithm . [ 1 ] It is a generalization of the special number field sieve : while the latter can only factor numbers of a certain special form, the general number field sieve can factor any number apart from prime powers (which are trivial to factor by taking roots). When the term number field sieve ( NFS ) is used without qualification, it refers to the general number field sieve. The principle of the number field sieve (both special and general) can be understood as an improvement to the simpler rat...