mersenneforum.org GNFS or SNFS for Fib(1009) ?
 Register FAQ Search Today's Posts Mark Forums Read

 2007-05-30, 16:11 #1 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 11001001101002 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 211-digit SNFS likely to be easier (using the Franke tools) than a 151-digit GNFS? I could check experimentally, but it would take about two CPU-weeks 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 146-digit unfactored part.
2007-05-30, 16:28   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by fivemack 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 211-digit SNFS likely to be easier (using the Franke tools) than a 151-digit GNFS? I could check experimentally, but it would take about two CPU-weeks 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 146-digit unfactored part.

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.

2007-05-30, 17:40   #3
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

255748 Posts

Quote:
 Originally Posted by R.D. Silverman 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.
Indeed.

My advice in such situations has always been to perform trial sieving with each algorithm. Sieve about 1e-4 of the special-q (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

 2007-05-30, 18:11 #4 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 645210 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 run-time 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.
2007-05-30, 19:48   #5
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22×112×23 Posts

Quote:
 Originally Posted by fivemack 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 run-time 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.
I was presupposing you'd found your polynomials...

Paul

 2007-08-06, 00:48 #6 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 22·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 All but the last two factors were already known. Method is SNFS, on the whole number, using the polynomial 5A^6 - 18A^5B + 30A^4B^2 - 20A^3B^3 + 15A^2B^4 + B^6 with A=Fibonacci(168) and B=Fibonacci(169), obtained by looking for short vectors in the lattice with an identity matrix on one side and [fib(1009),A^6,A^5B,...,B^5A,B^6] as final column. Small prime bound 2^24 on both sides, large prime bound 2^29 on both sides. Sieved special-Q values from 2^23 to 9*2^22, which took about 2500 CPU-hours, on two dual-core computers (one Core2Duo 2400MHz, one K8 2300MHz), taking most of July to get 42.6 million relations. Matrix-building 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 non-trivial dependencies, and factorised the number on the third square root attempt, with each square root taking about 70 minutes.
 2007-08-06, 07:25 #7 BotXXX     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

 Similar Threads Thread Thread Starter Forum Replies Last Post 2147483647 Factoring 2 2016-12-10 08:42 mdettweiler Factoring 15 2010-01-14 21:13 masser Sierpinski/Riesel Base 5 36 2008-04-18 02:39 schickel Factoring 0 2007-05-27 05:42 R.D. Silverman NFSNET Discussion 4 2007-04-11 20:39

All times are UTC. The time now is 16:59.

Fri Jan 21 16:59:25 UTC 2022 up 182 days, 11:28, 1 user, load averages: 1.93, 1.70, 1.66