GNFS or SNFS for Fib(1009) ?

[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.

[R.D. Silverman]

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.

[xilman]

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

[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.

[xilman]

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

[fivemack]

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.

[BotXXX]

Congratiolations with the successfull SNFS on F1009.
Hope to see the result soon on http://home.att.net/~blair.kelly/mat...i/history.html