mersenneforum.org About GNFS and size of smooth numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2014-11-03, 17:47 #1 JuanraG   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!
2014-11-03, 20:20   #2
R.D. Silverman

Nov 2003

22×5×373 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.

about how NFS works? There are some excellent surveys available on the net.

 2014-11-03, 22:05 #3 JuanraG   Nov 2014 28 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.
2014-11-03, 23:22   #4
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by JuanraG 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.
Learn how QS works first.

 2014-11-04, 01:07 #5 jasonp Tribal Bullet     Oct 2004 2×3×19×31 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.
2014-11-04, 01:41   #6
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

35·19 Posts

Quote:
 Originally Posted by JuanraG 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.

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.

2014-11-04, 12:20   #7
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
And in typical fashion, someone resorts to hyperbole in response to one of my posts.
One need not read 50 pages of academic papers. 5 pages of a Wikipedia article would have sufficed.

2014-11-04, 16:43   #8
chris2be8

Sep 2009

198010 Posts

Quote:
 Originally Posted by R.D. Silverman 5 pages of a Wikipedia article would have sufficed.
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

 Similar Threads Thread Thread Starter Forum Replies Last Post Sam Kennedy Factoring 5 2012-11-10 07:54 flouran Math 12 2009-12-25 16:41 CRGreathouse Math 3 2009-05-25 05:26 Citrix Math 9 2005-12-31 11:07 Yamato Math 1 2005-12-11 11:09

All times are UTC. The time now is 04:57.

Fri Jan 22 04:57:59 UTC 2021 up 50 days, 1:09, 0 users, load averages: 1.30, 2.03, 2.12