20141103, 17:47  #1 
Nov 2014
2 Posts 
About GNFS and size of smooth numbers
Hello,
I am new to GNFS and I am trying to understand how the polynomial selection affects to the complexity of the whole algorithm. 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. 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. 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? why is not possible build a fast GNFS with high d? I appreciate your help to understand this issue. Thanks so much! 
20141103, 20:20  #2  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
Polynomial selection affects the o(1) term in the L(N,c) function. Quote:
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. Quote:
Quote:
Error #2: Not understanding the algorithm. Quote:
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. 

20141103, 22:05  #3 
Nov 2014
2 Posts 
Wow!
I am sorry. I am not mathematician and it is hard for me to understand GNFS, even with all the surveys available on the net. I thought I could get some answers here but maybe this is a too advanced place for me. In any case, thank you for your explanation. It is clear to me now. Thaks so much. 
20141103, 23:22  #4  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:


20141104, 01:07  #5 
Tribal Bullet
Oct 2004
3555_{10} Posts 
The larger you choose d, the larger the algebraic polynomial degree. Each relation requires choosing (a,b) coordinates to plug into that larger polynomial, and as d increases the resulting values increase in size more and more quickly as the (a,b) values move away from the origin. So you essentially have a limited region in the (a,b) plane where the average size of the polynomial values are small enough that smooth relations are found often. As the number to be factored increases in size, the size of that nice region also increases and can support a (very slightly) larger d.
Thus, there is an optimal value of d that balances the rapidly increasing size of polynomial values with the temporary improvement in the smoothness probability. Many online papers go through the mathematics needed to determine that optimal d. 
20141104, 01:41  #6  
"Curtis"
Feb 2005
Riverside, CA
5639_{10} Posts 
Quote:
The answer you received illuminated something I hadn't considered about poly degree that optimal degree depends on input size, not on difficulty. That's why SNFS moves to degree 6 around 200 digits difficulty, just like GNFS does. If I recall the table from the published literature, does that mean degree 7 might be better than degree 6 for SNFS jobs around 350 digits? Anyway, thanks for asking, 'cause I learned something too. 

20141104, 12:20  #7  
"Bob Silverman"
Nov 2003
North of Boston
16524_{8} Posts 
Quote:
One need not read 50 pages of academic papers. 5 pages of a Wikipedia article would have sufficed. 

20141104, 16:43  #8 
Sep 2009
100101111011_{2} Posts 
That assumes they know which Wikipedia article to read. Gently pointing him to http://en.wikipedia.org/wiki/Quadratic_sieve http://en.wikipedia.org/wiki/Special_number_field_sieve and http://en.wikipedia.org/wiki/General_number_field_sieve would be better for a beginner.
Chris 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Not smooth enough numbers  Sam Kennedy  Factoring  5  20121110 07:54 
Distribution of Smooth Numbers  flouran  Math  12  20091225 16:41 
Smooth and rough numbers  CRGreathouse  Math  3  20090525 05:26 
Finding smooth numbers  Citrix  Math  9  20051231 11:07 
Smooth Numbers  Yamato  Math  1  20051211 11:09 