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
http://mathworld.wolfram.com/NumberFieldSieve.html , and
http://en.wikipedia.org/wiki/Number_Field_Sieve )
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:
Divide by 2, then 3, then 4, then 5, ... we only need to go up to the
square root of
N, and eavh division can be made in time (Log(N))2, for a running
time of
sqrt(N)*(Log(N))2.
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 10-digit numbers in one minute and multiply 10-digit numbers in 15 minutes (using pen and paper), you would take two minutes to add 20-digit numbers, and one hour to multiply two 20-digit 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 10-digit 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 100-digit or 200-digit number.
Claude