mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2013-02-22, 12:46   #34
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·2,861 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
henryzz is offline   Reply With Quote
Old 2013-02-22, 17:51   #35
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by henryzz View Post
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!
R.D. Silverman is offline   Reply With Quote
Old 2013-02-22, 18:19   #36
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
akruppa is offline   Reply With Quote
Old 2013-02-22, 18:21   #37
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×2,861 Posts
Default

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.
henryzz is offline   Reply With Quote
Old 2013-02-22, 18:28   #38
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160658 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
Dubslow is offline   Reply With Quote
Old 2013-02-22, 18:30   #39
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.

Last fiddled with by R.D. Silverman on 2013-02-22 at 18:30 Reason: fix pagination
R.D. Silverman is offline   Reply With Quote
Old 2013-02-22, 19:12   #40
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,529 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2013-02-22, 20:26   #41
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by jasonp View Post
Whether the CADO tools can handle world-record-size jobs is an open question;
This is work in progress.
akruppa is offline   Reply With Quote
Old 2013-03-14, 16:11   #42
Andi_HB
 
Andi_HB's Avatar
 
Mar 2007
Germany

23×3×11 Posts
Default

Quote:
Originally Posted by ryanp View Post
So, 50 days' work... not great, but not terrible either.
50 days are over - is the job done successfull?
Andi_HB is offline   Reply With Quote
Old 2013-03-14, 16:33   #43
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

2×7×13 Posts
Default

Almost there!

linear algebra completed 30676793 of 31289453 dimensions (98.0%, ETA 22h29m)
ryanp is online now   Reply With Quote
Old 2013-03-15, 19:49   #44
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

2·7·13 Posts
Default 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
ryanp is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
29 to 30 bit large prime SNFS crossover VBCurtis Factoring 11 2015-03-09 07:01
How many jobs should I run? Warlord Software 12 2013-10-11 22:18
Advice for large GNFS jobs? WraithX Factoring 59 2013-07-30 01:13
doing large NFS jobs on Amazon EC2? ixfd64 Factoring 3 2012-06-06 08:27
Filtering on large NFS jobs, particularly 2^908+1 bdodson Factoring 20 2008-11-26 20:45

All times are UTC. The time now is 22:11.

Wed Sep 30 22:11:13 UTC 2020 up 20 days, 19:22, 0 users, load averages: 1.50, 1.55, 1.53

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.