mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Advice for large SNFS jobs? (https://www.mersenneforum.org/showthread.php?t=17690)

henryzz 2013-02-22 12:46

[QUOTE=jasonp;330401]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.[/QUOTE]

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 2013-02-22 17:51

[QUOTE=henryzz;330450]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.[/QUOTE]

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 2013-02-22 18:19

[QUOTE=jasonp;330401]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.[/QUOTE]

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 2013-02-22 18:21

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 2013-02-22 18:28

[QUOTE=henryzz;330510]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. [/QUOTE]

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

R.D. Silverman 2013-02-22 18:30

[QUOTE=henryzz;330510] 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.
.[/QUOTE]

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: [b]so will the number of false hits[/b].
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 2013-02-22 19:12

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 2013-02-22 20:26

[QUOTE=jasonp;330517]
Whether the CADO tools can handle world-record-size jobs is an open question;[/QUOTE]

This is work in progress.

Andi_HB 2013-03-14 16:11

[QUOTE=ryanp;325647]So, 50 days' work... not great, but not terrible either.[/QUOTE]

50 days are over - is the job done successfull? :question:

ryanp 2013-03-14 16:33

Almost there!

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

ryanp 2013-03-15 19:49

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

[code]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[/code]


All times are UTC. The time now is 08:43.

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