16
$\begingroup$

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

$\endgroup$
6
  • 5
    $\begingroup$ 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? $\endgroup$
    – Gerry Myerson
    Commented Jan 27, 2013 at 0:23
  • $\begingroup$ @GerryMyerson I implemented Quadratic Field sieve but I don't really know any of the fields you mentioned. In a simple explanation, I expect to see an example of choosing two small polynomials, $f(x)$ and $f(g)$ with small degrees $d$ and $e$ that have a common root $m$ and show how do you find b-smooth pairs with them. It will be nice if you can also show how lattice sieving come in to play and reference other optimizations that one should consider. Basically, all I expect to see is an example. $\endgroup$
    – Ilya Gazman
    Commented Nov 27, 2017 at 21:01
  • 1
    $\begingroup$ @Ilya, have you checked the link in the answer given by user58512? $\endgroup$
    – Gerry Myerson
    Commented Nov 27, 2017 at 21:13
  • $\begingroup$ @GerryMyerson yes, of course, I been reading it several times. But I am a developer and I need to see the method in action in order to implement it(that's my actual goal). I have been reading wiki a lot and I saw some videos too. But I am in a place where there are many things that I don't understand and I don't know what I need to learn in more depth in order to figure it out. This is why I want to see some very simple clear example of how you pick the polynomials and spin them into b-smooth relations. $\endgroup$
    – Ilya Gazman
    Commented Nov 27, 2017 at 22:29
  • $\begingroup$ @Ilya, how about citeseerx.ist.psu.edu/viewdoc/… (Michael Case, A beginner's guide to the general number field sieve). $\endgroup$
    – Gerry Myerson
    Commented Nov 28, 2017 at 0:01

1 Answer 1

Reset to default
16
$\begingroup$

There's a brilliant writeup about this, other sieves and other factorization methods by Pomerance (who invented the quadratic sieve) http://www.ams.org/notices/199612/pomerance.pdf

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .