# Simply Explain the General Number Field Sieve

As a beginner to the world of integer factorization, my idea of factoring an integer is to generate a large list of prime numbers below this number and to repeatedly try to divide the integer by these primes. However for very large integers this method is useless.

It is known that the General Number Field Sieve is the "most efficient classical algorithm known for factoring integers larger than 100 digits", however not one article I came across explained it simply enough for me to understand.

Can you help me to understand the GNFS in simple terms and methods, and how to implement it on a large integer below $2^{64}$?

-
There are no large integers below $2^{64}$ --- you wouldn't use GNFS for anything that small. Also, there is a limit to how simple an explanation can be, and still be an explanation. To understand GNFS you must understand algebraic number fields; to understand those, you must understand Galois Theory, commutative algebra, and elementary number theory; to understand those, you must understand group theory, and linear algebra. So, what is your starting point? – Gerry Myerson Jan 27 '13 at 0:23