Factoring Lucas/Fibonacci numbers

log in

Advanced search

Message boards : NFS Discussion : Factoring Lucas/Fibonacci numbers

Author Message
VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1472 - Posted: 25 Jan 2015, 19:35:29 UTC

The current batch of Lucas/Fibonacci numbers to be factored by NFS@Home 15e (lasievee):
F1271 SNFS(265.3) - factored 2015-01-16 (p67*p162)
F1277 SNFS(266.5)
F1273 SNFS(266)
F1289 SNFS(269)
F1917 SNFS(267)
F1391 SNFS(269)
F1929 SNFS(269)

After this batch (quote Greg):


Looking at the list of remaining Fib/Luc numbers in range of 15e, after the current batch we have 1 quintic (L1397), 16 quartics (F1405, F1415, and 14 Lucas numbers from L2645A to L2855A/B), and 7 GNFS (F2145, F2163, F1585, L2037, L1502, L1583, and L1541)
http://mersenneforum.org/showpost.php?p=392123&postcount=1707

Lucas/Fibonacci numbers factorizations: http://mersennus.net/fibonacci/
Lucas numbers (wikipedia): http://en.wikipedia.org/wiki/Lucas_number
Fibonacci numbers (wikipedia): http://en.wikipedia.org/wiki/Fibonacci_number

Happy crunching,
Victor de Hollander

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1474 - Posted: 25 Jan 2015, 20:00:35 UTC

Fibonacci(1271) - 2015-01-16
6377465750724401911709385897327327486714371760226018682305241870181794762499038494326368861245989288801337220604247274599587538570185713843669993980009592793850322753164159897626397788780886671711135081366144892030091981752947521
(229 digits)

Poly:
5x^6 + 18x^5 + 30x^4 + 20x^3 + 15x^2 + 1
F211x-(F212)
SNFS(265.3)

Sieving: NFS@home 15e (you!)

Post-processing: Victor de Hollander
Using: Msieve 1.52 SVN(946) http://sourceforge.net/projects/msieve/ (developed by: Jason Papadopoulos)

Filtering
220,340,774 (raw) relations
167,759,587 unique relations
Target density 110
1 hour 40 min on a single core of a 3770k

Linear Algebra
matrix is 18,116,773 x 18,116,998 (7606.6 MB)
approximately 187 hours on 4 cores of a 3770k (HT off)

Square Root Phase
Factors found on dependency 1
prp67 factor: 8629458856911026988171887097293553366748448218019911277919355077829
prp162 factor: 739034261182775810732506246859987477634836887406986076848408389742670250721438511336333370636763970622157352164676981929084285802283833390894280372330219484419149
1 hour 19 min on a single core of a 3770k

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1475 - Posted: 25 Jan 2015, 20:24:36 UTC
Last modified: 25 Jan 2015, 20:25:17 UTC

Fibonacci(1277)
135988771045755502497914458919924958105224158599203245688678833974667972475546566225947586762919210486030227282324391147378584959395133027638085536599001495441035281614074424224968218599641200509100465689124910715736659396557118254538287919595921
(246 digits)

Poly
SNFS(266.5)

Sieving: NFS@home 15e (you!)

Post-processing: Victor de Hollander
Using: Msieve 1.52 SVN(946) http://sourceforge.net/projects/msieve/ (developed by: Jason Papadopoulos)

Filtering
13.8 GB (compressed file)
26.1 GB (uncompressed relations)
222,771,291 (raw) relations
174,628,992 unique relations
Target density 120 (too few cycles) and 115
2 hours 27 min (td=120)+ 2 hours 13 min (td=115) on a single core of a 3770k

Linear Algebra
matrix is 18,994,628 x 18,994,805 (8572.3 MB)
linear algebra at 0.0%, ETA 299h29m
I'll probably be on skiing holiday when LA will finish, so expect the factors in 2-3 weeks.

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1476 - Posted: 25 Jan 2015, 21:25:53 UTC - in response to Message 1474.

Fibonacci(1271) - 2015-01-16
matrix is 18,116,773 x 18,116,998 (7606.6 MB)
approximately 187 hours on 4 cores of a 3770k (HT off)

Correction: 246 hours
I forgot to add 59 hours after a resume

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1484 - Posted: 11 Feb 2015, 15:48:45 UTC

Fib(1277)

Linear algebra
approximately 299 hours on 4 cores of a 3770k

Square Root Phase
Factors found on dependency 2
prp96 factor: 275164198889975646704592158782170875786498595918766178531816232262038590545804360497024530701073
prp150 factor: 494209535958311884476480645319598771703342347015656651911184747169862444536393208817036966876914456200245628488446174760332525350754036004892880322177
2 hour 46 min on a single core of a 3770k

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1511 - Posted: 25 Mar 2015, 9:53:37 UTC

Fibonacci(1273)
197607181320763856728032145379539823934140263189304269275796412883221248578560933747669916096072379103143902440937785591275192958547589464937484015752073553526688302241413695388341584358013082757224542939861232516818180577 (222 digits)

Poly
SNFS(266)

Sieving: NFS@home 15e (you!)

Post-processing:
Filtering
15.2 GB (compressed file)
28.8 GB (uncompressed relations)
250,493,906 (raw) relations
186,438,142 unique relations
Target density 125
Took 3 hours on a single core of a 3770k

Linear Algebra
matrix is 15,871,614 x 15,871,839 (7360.9 MB)
Took 204 hours on 4 cores of a 3770k

Square Root Phase
Factors found on dependency 1
prp110 factor: 94554702678729108237561620220321830812445435410500398855200601202285589063658198434677220743475953602164370321
prp112 factor: 2089871531743680136145711450739785875555574194315590496625333744238935416215523170400127354304118909834153574737
Took 1 hour on a single core of a 3770k

Profile wreck2002
Send message
Joined: 5 Sep 09
Posts: 16
Credit: 26,898
RAC: 0
Message 1512 - Posted: 27 Mar 2015, 9:40:29 UTC - in response to Message 1511.
Last modified: 27 Mar 2015, 9:40:44 UTC

How much memory does this factorization taking?

Profile Carlos Pinho [TSBTs Pirate]
Volunteer moderator
Send message
Joined: 26 Sep 09
Posts: 162
Credit: 7,723,521
RAC: 0
Message 1513 - Posted: 27 Mar 2015, 16:16:00 UTC - in response to Message 1512.
Last modified: 27 Mar 2015, 16:24:08 UTC

How much memory does this factorization taking?


You need at least 16GB of memory and from the log file it used 8-9 GB (7360.9 MB) for the Linear Algebra phase. So 16GB so your computer doesn't stall.

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1514 - Posted: 5 Apr 2015, 16:27:04 UTC

Another one finished today:
Fibonacci(1289)
4132728977940963217361272530839994679608041769590746873740785092982818194076513395973317344423046827409892959118806400842320479435498780623348499956715868270786476953668756658286987615356118568389423987711601967454549387703657998763053 (235 digits)

SNFS(269)

Sieving: NFS@home 15e

Post-processing:
Filtering
15.1 GB (compressed file)
28.5 GB (uncompressed relations)
247,430,034 (raw) relations
178,384,144 unique relations
Target density 125 (failed) and 120
4-5 hours on a single core of a 3770k

Linear Algebra
matrix is 18800107 x 18800332 (8468.0 MB)
~296 hours on 4 cores of a 3770k

Square Root Phase
Factors found on dependency 1
prp56 factor: 11199326000261964507084574553000604250472428321503396841
prp180 factor: 369015865583722998868614496652293369306619478644462527427026126678548435718377809903317086020779491351201605163928373222077454728486053400528148387932508883516487010337581815015333
1.5 hours on a single core of a 3770k

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1515 - Posted: 5 Apr 2015, 16:33:34 UTC - in response to Message 1512.

How much memory does this factorization taking?

With matrices of 7-9GB, msieve uses 10-13GB RAM while doing the linear algebra. Add a GB or two for the operating system and you understand why 16GB is needed.

Profile wreck2002
Send message
Joined: 5 Sep 09
Posts: 16
Credit: 26,898
RAC: 0
Message 1516 - Posted: 6 Apr 2015, 15:54:42 UTC - in response to Message 1515.

Thanks for your reply.
I am going to factor 10^423-1 with Kurt and some others. Kurt has a 6 core 12 thread i7 with 16G memory using lpbr=32,it seems like that there is a risk of 16G memory not enough for this snfs 282.
I also curious for the next 16e candidaters of nfs@home,there is not enough gnfs Cunningham candidates left,so when switch to champion snfs ,for example snfs 350,whether 64G memory enough is a problem.

Profile Carlos Pinho [TSBTs Pirate]
Volunteer moderator
Send message
Joined: 26 Sep 09
Posts: 162
Credit: 7,723,521
RAC: 0
Message 1517 - Posted: 8 Apr 2015, 22:30:02 UTC - in response to Message 1516.
Last modified: 8 Apr 2015, 22:33:26 UTC

Thanks for your reply.
I am going to factor 10^423-1 with Kurt and some others. Kurt has a 6 core 12 thread i7 with 16G memory using lpbr=32,it seems like that there is a risk of 16G memory not enough for this snfs 282.


5,409- (SNFS 285.9) was factored few years ago by NFS@Home but used 33-bit LP's on both sides and most of the relations had 3 LP's on the rational side. Please check this post http://www.mersenneforum.org/showpost.php?p=232512&postcount=47 for matrix size and more details. Log of the post-processing is available.

I also curious for the next 16e candidaters of nfs@home,there is not enough gnfs Cunningham candidates left,so when switch to champion snfs ,for example snfs 350,whether 64G memory enough is a problem.


List can be found here:
http://homes.cerias.purdue.edu/~ssw/cun/who
I would also like to sieve for a champion SNFS but that's Greg decision plus to be checked ecm progress on difficult integers.

Carlos

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1518 - Posted: 10 Apr 2015, 22:24:40 UTC

Tom Womack finished post-processing of F1917:
http://mersenneforum.org/showpost.php?p=399821&postcount=139

F1917
12822859769061451024424290844490631828441395701506931406973666464310190719409306314478962383853872919527764814229341267015851996696775218179889438783027795678873944497977278314641553094083250475742093211835117 (209 digits)

245,365,882 (raw) relations
184,529,977 unique relations
Target Density 120

matrix is 15735827 x 15736051 (7135.3 MB)
173 hours on a 4 cores 4770k

Factors found on dependency 1
prp97 factor: 5154941018590613095470313627520233466354285373838297357573059243702655535561820405691535789361317
prp112 factor: 2487489133787855759937441100469924513133304968678686933166675460244639906134920171933200459145426861256159391401
1 hour 14 min on 1 core of a 4770k

Thanks to everybody who helped sieving and Tom Womack for post-processing.

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1521 - Posted: 13 Apr 2015, 23:27:35 UTC

The composite cofactor of F1941 was the product of 66-digit and 167-digit prime numbers:
P66=422038518557284382699679255814142222984522189008184457146957964617
P167=59907677831658702619810227141358693081586515127665495082811277179300789170066104213800373278422402100771262900719102341507021261326728863763864368894505269927632119857

The 16e V5 siever was used and the factorization completed on March 2.
The factors have been reported to the Fibonacci and Lucas Factorizations page.

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1522 - Posted: 15 Apr 2015, 10:14:55 UTC

F1391
898487023065726723189540642956262590085814279936675776451664374797802741696562456512201935536886671275947629205127678159826956392082308760427673583262603402456475511508884856558536492619311219182139177037614082243851762758680696577317068647481 (243 digits)

diff: SNFS(269)

Sieving: NFS@home 15e

Post-processing: Victor de Hollander
Filtering
15.4 GB (compressed file)
28.9 GB (uncompressed relations)
251,229,599 (raw) relations
186,465,749 unique relations
Target density 115 (125 and 120 failed)
4-5 hours on a single core of a 3770k

Linear Algebra
matrix is 16,098,260 x 16,098,485 (6963.9 MB)
~197 hours on 4 cores of a 3770k

Square Root Phase
Factors found on dependency 2
prp104 factor: 45457115500676341470273729401976620625732310534270877739621497116065657773353091084189122359991545865757
prp140 factor: 19765596940535270661728219213113463208044710605534270512002125208706350605197723322802462542175970718338613928177957788759622716460576707533
2 hours on a single core of a 3770k

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1524 - Posted: 25 Apr 2015, 17:01:24 UTC

F1929
10300516606249308141095598669371520434248238291636653606335488183012436994935752953371757047949189798215387969019601812876886691744501927812171448169720474731533243635932677247261709 (182 digits)

diff: SNFS(269)

Sieving: NFS@home 15e

Post-processing: Victor de Hollander
15.5 GB (compressed files)
29.1 GB (uncompressed relations)
255,158,127 (raw) relations
188,124,378 unique relations
Target density=125

Linear Algebra
matrix is 16,110,488 x 16,110,713 (7497.8 MB)
~209 hours on 4 cores 3770k

Square Root Phase
Factors found on dependency 1
prp82 factor: 2205948162915930188728253758406230768089063035987047653868064633322223630864596833
prp100 factor: 4669428221120836052207901829071262580709954000445036139624291939756122352739143892182753698617571373
1h14m single core 3770k

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1582 - Posted: 2 Sep 2015, 9:43:38 UTC

F1405 en F1415 are now queued on the 15e siever, it might be a while before you receive workunits. First there are a XYYXF (SNFS 261) and an Aliquot (GNFS194) to be done.

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1601 - Posted: 20 Oct 2015, 14:02:48 UTC

F1405 is fully factored
p58 factor: 2760658868161752397151556084505052457146474924423164947541
p63 factor: 155916003251865463312050460882181765664475933822047142492769161
p115 factor: 3708806696759426498601784197838963030603968213288115313873091782112769996865115868199195740302996516019045694936701

Thanks to Tom Womack for doing the post-processing.

Log can be found here:
http://mersenneforum.org/showpost.php?p=412844&postcount=414

F1415 is now being post-processed by Mike (Xyzzy), so I expect those factors in a week or two.

VictordeHollander
Send message
Joined: 23 May 11
Posts: 19
Credit: 319,168
RAC: 0
Message 1621 - Posted: 6 Dec 2015, 15:35:44 UTC
Last modified: 6 Dec 2015, 15:38:09 UTC

F1415 (15e siever)
SNFS(236)
prp63 factor: 703747967079103785555586774981303013102152381890476035037826061
prp174 factor: 106566721576496287067870961426304639399877346688737247908112975618116157769605593789289749500610860207534209900603129548233550352182201592522010012594460487455738863228718301

Thanks to M. Vang for doing the post-processing and to all who contributed CPU-cycles.

F2145 (14e siever)
GNFS(171)
prp75 factor: 567884411485455076613713834423034797343371558396358459401932772123099034821
prp96 factor: 389405627780364499759336865169250367148430992742093329546150486605821963974304803234775286115121

Logs can now be found by clicking on the links in the comments on the detailed siever stats pages.

L1397 is successfully sieved and M. Vang will do the post-processing, so expect those factors in 2 weeks or so.
F1297 is now queued on the 15e siever and should start sieving in the next month.

Message boards : NFS Discussion : Factoring Lucas/Fibonacci numbers


Home | My Account | Message Boards