Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$?

share|cite|improve this question
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

There's a brilliant writeup about this, other sieves and other factorization methods by Pomerance (who invented the quadratic sieve)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.