Quandaries
and Queries 

After looking at all the info I could get about NFS, I still have some questions that are unsolved: First of all: If someone found an algorithm that has a worst case running time of N*Log(N) to factor an integer n into his divisors, would it be quicker or slower then the number field sieve algorithm? secondly, what exactly is the time complexity of the Number Field Sieve algorithm, if I would factor an integer n? and finally: how should I "interpret" the `EXP` i constantly
see in the time complexity for the number field sieve algorithm (see many thanks! 

Hi, Slower I think: I am not
an expert on the number field sieve algorithm, but the running time
you propose seems to be slower than trial division:
You can view Log(N) as a measure of the order of magnitude of the NUMBER OF DIGITS of N. This measure is used to measure the running time of the usual arithmetic operations. For instance, addition is linear and multiplication is quadratic (with the usual method), which means that if you can add 10digit numbers in one minute and multiply 10digit numbers in 15 minutes (using pen and paper), you would take two minutes to add 20digit numbers, and one hour to multiply two 20digit numbers. In asymptotic notation this means that adding numbers as large as N is O(Log(N)) and multiplying numbers as large as N is O(Log(N)^{2}). Compared to this, the exponential function EXP is very large: EXP(Log(N)) = e^{(Log(N))} = N. This would be the running time of an unsophisticated addition algorithm which would add two numbers A and B by setting the total at A and then counting up from 1 to B, adding 1 to the total at every count. For 10digit numbers, this would take more than a lifetime. So, algorithms as slow as O(EXP(Log(N)) are too slow for practical purposes. The trial division algorithm given above is O(sqrt(N)*Log(N)^{2}) = O(EXP( Log(N)/2 + 2Log(Log(N)))), and this is still too slow. In the arguments of the EXP function, the double logarithm terms correspond to "something that looks like the number of digits of N" while the simple logarithm terms correspond to "something like N itself". Even with small constant multiples or small exponents, these terms tend to make the algorithm impractical when N is a 100digit or 200digit number. Claude 

