What is the roots of NFS algorithm?
 

I am new to this forum as to the math this life and world:)
However i am very interested in math and espechially in factoring and prime numbers.. may be I could even say in hole number theory(Fermatt theorem and so on:)..
Keep in mind that this however doesn`t meens that i can be considered as profesional in this field.. My knowledge level in math actually is only raches high-school level(as does my current level of education)..
I have treid to write some algorithms for both searching primes and factoring numbers.. Once I allready thought i have discovered great new algorithm - however after a little of search through the internet i was dissapointed to see that Eratostenes somewhear near 300B.C. discovered exactly the same:)) {and he even had a more optimized version of "my" algorithm}.. Other my algorithms in number factoring aren`t quite efective and for now they hardly can beat trail factoring..
OK If you aren`t already bored by this and are still reading i would like toask to somone if he can explain NFS(GNFS) algorithm so I could at least understand basics of this algorithm.. Only please try to be as simple as you can during you try to explain me it.. Because if you say something that is understandable only by those who can handle highest-math then i doubt i will even be able to read this through:)..

I suggest you buy yourself a basic introduction to number theory and related algorithms - for instance Hans Riesel's "Prime Numbers and Computer Methods for Factorization." If you're still at the sieve-of-Eratosthenes stage, there is a [b]lot[/b] of material you need to educate yourself on before you have a chance of understanding algorithms like NFS. This isn't like "The Matrix," where you can instantly learn this stuff by popping in a CD-ROM or taking a pill. It takes lots of work - not a popular notion in this one-click era, I realize.

about my knowledege in math it isnt as simple as good or bad..
I may be lack knowledge in mathemathical terms and because of that i can`t read math code fast and fluent.. Because of that I cant` understand even some statements..
But thats not to say that i don`t know anything about math.. Sieve of Eratostenes of course is simple but still as i understood it is fastest algorithm to date to store all little primes in a row.. Of course modern math includes many new ideas and lots of them are dificult to understand because there are much diferent terms that i don`nt know about..
However.. that is why i asked to try to explain NFS alghorithm simply and from the beggining.. I just wish to understand ideas on what is based this alghorithm.. and i think it can be done if someone explains it with steb by step method..
It is said :" Only that who understands compleetly all can explain to everyone it so, that noone understands anything".. :) however i disagree to this.. and i think that only that who really understand can explain simple and clear.... of course may be it will still be hard to me, but i am ready to try..

The best general (short) introduction to computational factoring which I have found is [url=ftp://ftp.cwi.nl/pub/pmontgom/cwisurvey.psl.gz]"A Survey of Modern Integer Factorization Algorithms"[/url] by Montgomery (1994). The last section describes the NFS. I would suggest reading it all the way through at least once, and then focus more on the parts which interest you or which you find difficult.

To read the file, you will need a postscript reader and a program to extract gzipped files.

I'd also recommend [url]http://www.math.uoc.gr/~marios/papers/etd.pdf[/url].

I can try to give an overview, but to understand NFS properly requires a fairly deep mathematical knowledge.

To start, lets assume that the number N that we are trying to factor is the product of two primes: N = p*q. The method works if there are more than 2 prime factors but it needlessly complicates the explanation if we try for complete generality.

First we remember the equation a^2-b^2 = (a+b) * (a-b). So, if we can represent N as the difference of two squares we instantly have a factorization of N. This condition can be relaxed somewhat. If a multiple of N can be so represented we have that k*N = (a+b)*(a-b). If we're lucky, the factorization will split N and not only k. This relaxed condition is the same as saying a^2 = b^2 modulo N.

Now it's very difficult to find two squares such that a^2 = b^2 mod N but there are easier relationships that can be found. If it wasn't difficult to find squares with that relationship, it wouldn't be difficult to factor N.

What the number field sieve does, in common with a number of other algorithms such as the quadratic sieve, is find large quanties of numbers which are "smooth" and attempts to piece together some of these number in such a way that they form a square modulo N. The technical term "smooth" means that such a number factors entirely into small primes.

For the remainder of the explanation, I'm going to gloss over an enormous amount of deep mathematics. Mathematicians will have to forgive me and/or produce a better explanation.

Some of the data input into the NFS algorithm, as well as N, is the specification of two (or more, but lets keep it a simple as possible) polynomials. If you don't know what a polynomial is, you don't have a hope in hell of understanding what's going on so I won't even try to define that term.

As the algorithm progresses, the two polynomials are evaluated, modulo N, at a very large number of points. If the two values at a point are both simultaneously smooth (factor entirely into small primes, remember) then the combination of the point and its factorization is called a relation. In practice, relations are found by a process which is rather similar to the way in which primes are found in the sieve of Eratosthenes. This is the origin of the word "sieve" in the Number Field Sieve. I am not going to explain where the "Number Field" comes from as that takes us too deep into the underlying mathematics.

Eventually, we will collect a very large number of relations. When there are enough of them, there's the possibility that multiplying some of them together will mean that all the primes in the underlying factorizations will occur an even number of times. An even number of primes in a factorization indicates that the quantity is a square. Squares are good. If we can arrange that the values of [b]both[/b] polynomials are simultaneously square, we can find a corresponding representation of a multiple of N as the difference of two squares.

Finding a set of relations such that the primes in the underlying factorizations occur an even number of times is done by the so-called filtering and linear algebra stages (the latter is sometimes called the matrix stage). This gives us k*n = a^2-b^2.

Extracting the square root of an ordinary integer is relatively easy. In the NFS, however, the quantities a^2 and b^2 are not ordinary integers. They are algebraic integers which lie in an algebraic number field and I'm not going to explain what that means. Suffice it to say that extracting square roots is far from trivial and the "square root stage" takes a significant amount of computation. Once it has been performed, we do indeed know a+b and a-b, which are both factors of k*N.

Of course, we may not get luck and the factorization may splt k instead of N. Not to worry: we collected lots of relations from the sieving stage, far more than we actually need, so we find another set with the correct properties and try again. In fact, the linear algebra stage generally finds dozens of such sets. As each set has a 50% chance of splitting N, we are going to get lucky quite rapdly in practice. There's less than one chance in a thousand that we need more than ten sets and less than one in a million that we need more than twenty.

That's pretty much the best I can do to explain the NFS with a minimum of math.

Paul

Thanks so much Paul,

You certainly are a good teacher. It will be much easier now, for most people, to get the big picture.

Joss

Thanks to Paul for that nice non-technical description of NFS. Paul neglected to point out that the idea of factoring a number N by way of finding congruences a^2 = b^2 mod N actually dates back to Fermat, and the study of the thusly-named Fermat Factoring Method (FFM, for short) is a good starting point for working one's way up through its successors, the Quadratic Sieve (the multiple polynomial variant of the latter was used for the famous factorization of RSA129) and the Number Field Sieve.

FFM has the limitation that it is only practical when N factors into two roughly equal-sized pieces, i.e. (a+b) and (a-b) are similar in size. One can think (in very crude terms) of QS and NFS as being ways to get around this restriction. Interestingly, NFS in fact doesn't care one whit about the relative sizes of the factors (nor even about the number of factors of N) - the work is the same irrespective of these properties. In that sense FFM actually possesses a property which NFS lacks, and which is desirable for RSA-style factorizations, i.e. those for which the number is known in advance to be the product of two similar-sized factors. However, for RSA-sized numbers even a pair of factors which are within a factor of 2 of each other in size is still practically impossible for FFM. It would be wonderful indeed if someone could find a clever way of modifying NFS to be able to benefit from the closeness of factors of N, i.e. to preserve the worst-case asymptotic speed of the algorithm, but to speed things up even further when the ratio of the factors of p/q is not too far from unity.