20070530, 16:11  #1 
(loop (#_fork))
Feb 2006
Cambridge, England
1100100110100_{2} Posts 
GNFS or SNFS for Fib(1009) ?
Fib(1009), the smallest unsplit Fibonacci number, has 211 digits. It has been quite thoroughly ECMed and about 60 digits of small factors have been removed, leaving a C151.
If we let A = Fib(168) and B = Fib(169), then fib(1009) = 5*A^6  18*A^5*B + 30*A^4*B^2  20*A^3*B^3 + 15*A^2*B^4 + B^6 ; so SNFS is possible. Is a 211digit SNFS likely to be easier (using the Franke tools) than a 151digit GNFS? I could check experimentally, but it would take about two CPUweeks to hunt a decent polynomial for the C151, which seems a fair amount of wasted effort to put in if other people have experience which gives the answer 'do SNFS'. My guess is that SNFS is the right answer, in that the S200 that I've sieved but been unable to solve took about the same length of time as a C135, and eleven more digits will add less to the time of an SNFS than of a GNFS job. A more difficult question is then Lucas(1021), which is of 214 digits, SNFSable by A=fib(170), B=fib(171), lucas(1021)=B^6 + 12*B^5*A  15*B^4*A^2 + 60*B^3*A^3  60*B^2*A^4 + 42*B*A^5  11*A^6, and has a 146digit unfactored part. 
20070530, 16:28  #2  
Nov 2003
2^{2}×5×373 Posts 
Quote:
For F1009, I expect SNFS to be slightly easier. For L1021, I expect GNFS to be slightly easier. But the decision is close in both cases. 

20070530, 17:40  #3  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
25574_{8} Posts 
Quote:
My advice in such situations has always been to perform trial sieving with each algorithm. Sieve about 1e4 of the specialq (or b if using a line siever) and see which would complete the faster. If there's still no significant difference, you've wasted an hour or two and can choose whichever you want. If there is a significant difference you may have saved a week or two over making the wrong choice. Pau 

20070530, 18:11  #4 
(loop (#_fork))
Feb 2006
Cambridge, England
6452_{10} Posts 
Trial sieving's obviously the answer if you're trying to decide between two SNFS polynomials, or to pick how big large and small primes should be, and I've even got some perl scripts to do that work for me.
I'm just unsure how realistic trial sieving with a polynomial obtained by running Kleinjung's tool for an hour is going to be as a prediction of the runtime with a polynomial obtained by running Kleinjung's tool for a month. If the bad GNFS beats the SNFS then a good one obviously will; if it loses then I'm not sure I learn much. 
20070530, 19:48  #5  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2^{2}×11^{2}×23 Posts 
Quote:
Paul 

20070806, 00:48  #6 
(loop (#_fork))
Feb 2006
Cambridge, England
2^{2}·1,613 Posts 
Completed by SNFS 06 August
Code:
Fibonacci(1009) = P4 2017 P6 732533 P7 5091413 P16 2152222831158769 P29 55237728336499770684561118541 P67 1917966647364357389248209734912103556444225816382250644823598319933 P85 1926231567882512101883690436059725849373269373519745173514065568709142680990835085409 Small prime bound 2^24 on both sides, large prime bound 2^29 on both sides. Sieved specialQ values from 2^23 to 9*2^22, which took about 2500 CPUhours, on two dualcore computers (one Core2Duo 2400MHz, one K8 2300MHz), taking most of July to get 42.6 million relations. Matrixbuilding started by using my own tools for duplicate and singleton removal; duplicate removal got down to 32.4M relations, first stages of singleton removal got to 24.283M relations, and then I handed over to Jason Papadopoulous's msieve code. This took about an hour and a half on one CPU of the Core2 to build a 3719711*3719958 matrix with a sparse part of weight 246952461, 45 hours on one CPU (I ran the threaded version but one CPU was occupied 24/7 by a different SNFS job finding the factor 60122581024264630176709254473102292605236790972666567 of 7^191+6^191) to find 46 nontrivial dependencies, and factorised the number on the third square root attempt, with each square root taking about 70 minutes. 
20070806, 07:25  #7 
Aug 2003
Europe
2×97 Posts 
Congratiolations with the successfull SNFS on F1009.
Hope to see the result soon on http://home.att.net/~blair.kelly/mat...i/history.html 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
What should the "q" value increase to for GNFS/SNFS computations?  2147483647  Factoring  2  20161210 08:42 
SNFS polynomials for k*b^n+1  mdettweiler  Factoring  15  20100114 21:13 
fun with snfs  masser  Sierpinski/Riesel Base 5  36  20080418 02:39 
Completed my first SNFS job  schickel  Factoring  0  20070527 05:42 
SNFS Polynomial  R.D. Silverman  NFSNET Discussion  4  20070411 20:39 