View Single Post
Old 2014-11-03, 17:47   #1
Nov 2014

28 Posts
Default About GNFS and size of smooth numbers


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!
JuanraG is offline   Reply With Quote