mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2016-10-04, 22:38   #111
WraithX
 
WraithX's Avatar
 
Mar 2006

11·43 Posts
Default

I was recently asked about the status of HP49 119 c251, and wanted to update everyone. I'd also like to ask if anyone here on the forum would help me tackle this number with GNFS?

First, the work I've done so far can be summed up with the following tables:
Code:
HP49 Step 119 c251:
Expected number of curves to find a factor of n digits:
      digits           35        40       45      50       55        60        65        70        75
------------------------------------------------------------------------------------------------------
    B1 =  11e6        138       788     5208   39497   336066   3167410  3.2e+007  3.7e+008
    B1 =  43e6         61       278     1459    8704    57844    419970   3346252  2.9e+007
    B1 = 260e6         23        82      335    1521     7650     42057    250476   1603736
    B1 =   1e9         14        44      154     599     2553     11843     59619    319570
    B1 =   3e9         11        31       96     335     1279      5292     23661    112329    565999
    B1 =   3e9         11        31       99     344     1315      5446     24234    115138    580561 (-maxmem 4096)

Number of curves completed so far, and their equivalent t-level:
 12000 @  11e6 =   86.956x   15.228x   2.304x   0.303x   0.035x    0.003x
 18000 @  43e6 =  295.081x   64.748x  12.337x   2.068x   0.311x    0.042x   0.005x
 90000 @ 260e6 = 3913.043x 1097.560x 268.656x  59.171x  11.764x    2.139x   0.359x   0.056x
120000 @   1e9 = 8571.428x 2727.272x 779.220x 200.333x  47.003x   10.132x   2.012x   0.375x
 16000 @3e9(4g)= 1454.545x  516.129x 161.616x  46.511x  12.167x    2.937x   0.660x   0.138x
 19200 @   3e9 = 1745.454x  619.354x 200.000x  57.313x  15.011x    3.628x   0.811x   0.170x
----------------------------------------------------------------------------------------------
                16066.507x 5040.291x 1424.133x 365.699x 86.291x   18.881x   3.847x   0.739x
I forget when I generated the table of needed curve counts, but those are the numbers I'll be sticking with for this work. So, according to the e^(-x) rule, we can say that the chance of a missed factor for the 55+ digit level is:
Code:
55-digits: e^(-86.291) ~= 3.344e-38
60-digits: e^(-18.881) ~= 6.310e-9
65-digits: e^(-3.847)  ~= 0.0213
70-digits: e^(-0.739)  ~= 0.4775 (almost 50%!)
I'm still creating and processing a lot of curves at B1=3e9, but it might be time to switch to GNFS if I can get enough help here on the forum. Perhaps we could get ryanp, and NFS@Home, and some teams organized by pinhodecarlos to finish this up within the next year? That would certainly be the best case, but I think any one of those 3 sources would help put a huge dent in the amount of GNFS sieving we would need to do. Let me know if there is interest in working on this number and what sort of schedule would work best for everyone.
WraithX is offline   Reply With Quote
Old 2016-10-05, 02:54   #112
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

111748 Posts
Default

I'll donate a few hundred ECM curves, as I have grown tired of M1277 ECM work.

While the sieving is intimidating, the matrix is what should concern you when contemplating this job. I saw your GNFS-210 was 77M matrix; a WAG that matrix size continues to scale with job size has a GNFS-170 around 9M, so perhaps a GNFS-250 would have a matrix on the order of 300M by 300M? Perhaps 400M? Memory needs scale with the square of the dimension, so 30-40 times more memory than the 32GB you needed for GNFS-210. A terabyte of RAM might do it?

Two questions for the big-job experts:
1. When matrix-solving on a cluster, does each node need only its portion of the matrix in memory? That is, if a 1TB-ram job were split onto 32 nodes, would each node need something less than 64GB?

2. Do the CADO tools have an equivalent of lasieve-17e?
VBCurtis is online now   Reply With Quote
Old 2016-10-05, 03:02   #113
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Err... pardon me, but wouldn't this set the (public) record for largest GNFS factorization ever? This counts out at 834 bits, rather more than the current 768 record (...unless 896 is in progress by the Paul Zimmerman group?)
Dubslow is offline   Reply With Quote
Old 2016-10-05, 15:16   #114
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67208 Posts
Default

Yes, it would be a record for public factorizations.

The memory usage of the matrix scales linearly with the dimension for these kinds of problems, because we store it in sparse format.Spreading the linear algebra over multiple machines means the matrix is cut up into parts and each machine sees only its local part; vectors are shuttled back and forth between machines as the computation needs them.

I would be worried about the filtering instead. The final sieving dataset would have several tens of billions of relations and this is far larger than what either CADO or Msieve has ever processed. Msieve still has a bug that limits filtering to about a billion relations; even without the bug, more than 4 billion relations would require major plumbing changes to the code.
jasonp is offline   Reply With Quote
Old 2016-10-05, 17:31   #115
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

131516 Posts
Default

Quote:
Originally Posted by jasonp View Post

I would be worried about the filtering instead. The final sieving dataset would have several tens of billions of relations and this is far larger than what either CADO or Msieve has ever processed. Msieve still has a bug that limits filtering to about a billion relations; even without the bug, more than 4 billion relations would require major plumbing changes to the code.
Do you have spare time to start working on it?!
pinhodecarlos is offline   Reply With Quote
Old 2016-10-05, 18:35   #116
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

24×13×17 Posts
Default

That wasn't volunteering :(
jasonp is offline   Reply With Quote
Old 2016-10-05, 18:54   #117
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

5·977 Posts
Default

Quote:
Originally Posted by jasonp View Post
That wasn't volunteering :(
I really would like to see a new factoring record by NFS@Home.

With regards to HP49 119 c251 maybe we can set an ecm forum effort...thoughts please?
pinhodecarlos is offline   Reply With Quote
Old 2016-10-05, 22:02   #118
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22×7×132 Posts
Default

I think you should run some curves, so you can call it a forum effort.

The filtering would have to be done by CADO; there's no reason to think CADO can't handle it, except for the obvious fact that it hasn't been tested on such a problem. M1177 SNFS job has 15G raw relations, so we know there is no 4G limit.

Those huge Mersenne factorizations used 37-bit large primes, 3 rational large primes (109-bit mfbr) 2 algebraic. We could test-sieve 37 vs 38 vs 39 bit large primes? If CADO can run a sieve region bigger than 16e equivalent, the sieve step is mere CPU time (right, guys? Guys?).

Last fiddled with by VBCurtis on 2016-10-05 at 22:13
VBCurtis is online now   Reply With Quote
Old 2016-10-06, 10:54   #119
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

29·367 Posts
Default

Quote:
Originally Posted by pinhodecarlos View Post
I really would like to see a new factoring record by NFS@Home.

With regards to HP49 119 c251 maybe we can set an ecm forum effort...thoughts please?
I, or anyone else for that matter, could easily set up an ECMNET server.

Note that C251 is within range of GPU stage 1. Perhaps someone would like to write a V2 ecmclient compatible wrapper. It's something I've been thinking about for a long time but the global shortage of round tuits has hit hard.
xilman is offline   Reply With Quote
Old 2016-10-06, 12:25   #120
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5×1,171 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
I think you should run some curves, so you can call it a forum effort.

The filtering would have to be done by CADO; there's no reason to think CADO can't handle it, except for the obvious fact that it hasn't been tested on such a problem. M1177 SNFS job has 15G raw relations, so we know there is no 4G limit.

Those huge Mersenne factorizations used 37-bit large primes, 3 rational large primes (109-bit mfbr) 2 algebraic. We could test-sieve 37 vs 38 vs 39 bit large primes? If CADO can run a sieve region bigger than 16e equivalent, the sieve step is mere CPU time (right, guys? Guys?).
There is a little bit of questions whether 18e would be needed for 251 digits. 15e has done up to 194 digits and 16e has done up to 220 digits. That is a difference of 26 digits. 252-220=32. Maybe 16e could be stretched further. I would hope that 17e would be enough.
It looks like the cado siever supports fb primes >32 bits and large primes >32 bits.

The CADO siever used to have a SUPPORT_I17 configuration. This has now been removed. I assume that it always supports it now. I can't find any limitation in the code.

Last fiddled with by henryzz on 2016-10-06 at 12:26
henryzz is online now   Reply With Quote
Old 2016-10-06, 14:20   #121
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

473210 Posts
Default

RSA-768 was done with 16e (equivalent, CADO). The CADO defaults for siever region use smaller sievers than we usually do with lasieve; e.g. 13e into the mid 140s GNFS. 251 would be right at the top of 17e even if 18e was available; test-sieving would be fun, right?
VBCurtis is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P-1 on M1061 and HP49.99 ATH Factoring 21 2009-10-13 13:16

All times are UTC. The time now is 21:56.

Tue Apr 13 21:56:57 UTC 2021 up 5 days, 16:37, 1 user, load averages: 2.11, 2.20, 2.00

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.