mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-05-30, 16:11   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11000111010112 Posts
Default 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.
fivemack is offline   Reply With Quote
Old 2007-05-30, 16:28   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-05-30, 17:40   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3×112×29 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
xilman is offline   Reply With Quote
Old 2007-05-30, 18:11   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,379 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2007-05-30, 19:48   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3×112×29 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
xilman is offline   Reply With Quote
Old 2007-08-06, 00:48   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

637910 Posts
Default 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.
fivemack is offline   Reply With Quote
Old 2007-08-06, 07:25   #7
BotXXX
 
BotXXX's Avatar
 
Aug 2003
Europe

2×97 Posts
Default

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

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 2016-12-10 08:42
SNFS polynomials for k*b^n+-1 mdettweiler Factoring 15 2010-01-14 21:13
fun with snfs masser Sierpinski/Riesel Base 5 36 2008-04-18 02:39
Completed my first SNFS job schickel Factoring 0 2007-05-27 05:42
SNFS Polynomial R.D. Silverman NFSNET Discussion 4 2007-04-11 20:39

All times are UTC. The time now is 06:00.

Thu Jan 28 06:00:43 UTC 2021 up 56 days, 2:12, 0 users, load averages: 2.29, 2.41, 2.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.