View Single Post
Old 2014-11-03, 20:20   #2
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22·5·373 Posts

Originally Posted by JuanraG View Post

I am new to GNFS and I am trying to understand how the polynomial selection affects to the complexity of the whole algorithm.
Have you actually read any articles about how it works?

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

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".

Try Google.

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.

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.

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.

May I suggest that before you return to this discussion that you actually read some articles
about how NFS works? There are some excellent surveys available on the net.
R.D. Silverman is offline   Reply With Quote