Advice for large SNFS jobs?

[henryzz]

Originally Posted by jasonp

The CADO code also includes a tremendously fast ECM/P+-1 implementation for up to 126 bit operands (two 64-bit words max) that Alex reports is even faster than the MPQS code in the Franke/Kleinjung sievers.

How does the rest of the siever compare? It shouldn't be that hard to replace the large prime factoring code in the ggnfs siever if necessary.

[R.D. Silverman]

Originally Posted by henryzz

How does the rest of the siever compare? It shouldn't be that hard to replace the large prime factoring code in the ggnfs siever if necessary.

A worthwhile endeavor!!!!!

If NFS@Home has reached the limits of GGNFS, what about trying the CADO
tools instead? Let's try to improve capabilities!

[akruppa]

Originally Posted by jasonp

The CADO code also includes a tremendously fast ECM/P+-1 implementation for up to 126 bit operands (two 64-bit words max) that Alex reports is even faster than the MPQS code in the Franke/Kleinjung sievers.

It was a bit faster when I visited EPFL a few years ago. However, I have not worked on that code since, while Thorsten probably worked on his, and I have no idea how they compare with newer lasieve versions.

[henryzz]

If you read above we are working out ways of extending those limits. Correct me if I am wrong but I don't think cado has something capable of replacing msieve for this size job. It looks like above that msieve will soon be our limitation. Putting the cado ecm into ggnfs is purely an easy speedup not an extension of capability.
Eventually I imagine the ggnfs siever will be a problem because of its limitted sieve area but not yet.

[Dubslow]

Originally Posted by henryzz

If you read above we are working out ways of extending those limits. Correct me if I am wrong but I don't think cado has something capable of replacing msieve for this size job.

Hmm... as I recall it was CADO tools which post-processed M1061.

[R.D. Silverman]

Originally Posted by henryzz

It looks like above that msieve will soon be our limitation. Putting the cado ecm into ggnfs is purely an easy speedup not an extension of capability.
.

I disagree. It should, in theory, result in an extension of capability.

If one keeps the size of the sieve area fixed, but increases the sizes of the
factor bases, then the yield per special-q over the fixed sieve region will
increase. The problem is: so will the number of false hits.
You will get more cofactors that do not split into primes less than the large prime bounds.

It will take extra time to dispose of these false hits. A faster method of
splitting the cofactors will alleviate this difficulty.

[jasonp]

M1061 was postprocessed with Msieve.

The CADO postprocessing code is perfectly capable of handling large jobs; it was used to factor RSA704, which generated a matrix almost as large as what Greg needed for M1061. In fact the dataset for RSA704 was undersieved and Msieve couldn't handle the lack of excess relations. Each package has different strengths.

Whether the CADO tools can handle world-record-size jobs is an open question; I can tell you that Msieve surely cannot.

[akruppa]

Originally Posted by jasonp

Whether the CADO tools can handle world-record-size jobs is an open question;

This is work in progress.

[Andi_HB]

Originally Posted by ryanp

So, 50 days' work... not great, but not terrible either.

50 days are over - is the job done successfull?

[ryanp]

Almost there!

linear algebra completed 30676793 of 31289453 dimensions (98.0%, ETA 22h29m)

[ryanp]

And, here it is. (2801^83-1)/2800 factors into a 93 digit prime and a 191 digit prime:

Fri Mar 15 09:30:52 2013  lanczos halted after 494801 iterations (dim = 31289229)
Fri Mar 15 09:31:36 2013  recovered 34 nontrivial dependencies
Fri Mar 15 09:31:36 2013  BLanczosTime: 59328
Fri Mar 15 09:31:36 2013  elapsed time 16:28:51
Fri Mar 15 09:45:42 2013  
Fri Mar 15 09:45:42 2013  
Fri Mar 15 09:45:42 2013  Msieve v. 1.50 (SVN exported)
Fri Mar 15 09:45:42 2013  random seeds: e392a192 464a7410
Fri Mar 15 09:45:42 2013  factoring 4784427753962229503583191777575386925462640502543527013793934480234680863804447852383959785408791045459809147067083157248015897910382151758867576620242257524246139326208569043470479714282260046673050230392057658284742406595942226610043596316622243579005395853667131475327572196568483 (283 digits)
Fri Mar 15 09:45:44 2013  searching for 15-digit factors
Fri Mar 15 09:45:45 2013  commencing number field sieve (283-digit input)
Fri Mar 15 09:45:45 2013  R0: -1829715316371090533839726975772594414416841479201
Fri Mar 15 09:45:45 2013  R1: 1
Fri Mar 15 09:45:45 2013  A0: -2801
Fri Mar 15 09:45:45 2013  A1: 0
Fri Mar 15 09:45:45 2013  A2: 0
Fri Mar 15 09:45:45 2013  A3: 0
Fri Mar 15 09:45:45 2013  A4: 0
Fri Mar 15 09:45:45 2013  A5: 0
Fri Mar 15 09:45:45 2013  A6: 1
Fri Mar 15 09:45:45 2013  skew 3.75, size 4.527e-14, alpha -1.144, combined = 1.075e-14 rroots = 2
Fri Mar 15 09:45:45 2013  
Fri Mar 15 09:45:45 2013  commencing square root phase
Fri Mar 15 09:45:45 2013  reading relations for dependency 1
Fri Mar 15 09:46:27 2013  read 15644347 cycles
Fri Mar 15 09:46:53 2013  cycles contain 43719780 unique relations
Fri Mar 15 10:00:12 2013  read 43719780 relations
Fri Mar 15 10:06:03 2013  multiplying 43719780 relations
Fri Mar 15 11:00:53 2013  multiply complete, coefficients have about 1248.28 million bits
Fri Mar 15 11:00:58 2013  initial square root is modulo 397633
Fri Mar 15 12:40:46 2013  sqrtTime: 10501
Fri Mar 15 12:40:46 2013  prp93 factor: 320275002207928618516974240639287722386404036901633806415927872193124566002965261773254007319
Fri Mar 15 12:40:46 2013  prp191 factor: 14938498855605621302344771462931389549628225945089317981474820437041872729327482659006891215676069205302760273883150980375684105951144826837014488372171976593391874894148865313908766630812757
Fri Mar 15 12:40:46 2013  elapsed time 02:55:04