View Single Post 2014-11-03, 20:20   #2
R.D. Silverman

Nov 2003

746010 Posts Quote:
 Originally Posted by JuanraG Hello, I am new to GNFS and I am trying to understand how the polynomial selection affects to the complexity of the whole algorithm.

Polynomial selection affects the o(1) term in the L(N,c) function.

Quote:
 I read that GNFS is fastest than MPQS for huge numbers because GNFS has to find smooth numbers of size about N^(1/d), being d the order of the polynomial.
You misread. Each relation consists of TWO smooth numbers. One of which is indeed about N(1/d). The other number
is about P^d where P is an 'average' coordinate for a lattice point. While N^1/d does reduce with increasing d, the other side
increases (even faster) as d increases. One finds a value of d such that the probability of both being smooth SIMULTANEOUSLY
is as large as possible.

You are also confusing "size" with "magnitude".

Quote:
 I read also that finding a good polynomial is a time consuming operation, but I don't understand why is not enough for improve the speed of the algorithm the selection of a high value of d.
I explain this just above.

Quote:
 My intuition says that with a polynomial with a very high d we will have to find small smooth numbers and this is much fast that finding smoth numbers of order N^(1/3), for example. Where is my error?
Error #1: Assuming you know enough to HAVE an intuition. Classic Dunning and Kruger.
Error #2: Not understanding the algorithm.

Quote:
 why is not possible build a fast GNFS with high d?
Who says that it isn't? The optimal d increases with N. One wants large d for very large N.
The difficulty, of course, is that the amount of computation required for such N is beyond computer capabilities
for the immediate future.  