20190826, 19:10  #1 
Oct 2018
2^{3}·3 Posts 
Factorization factory
Hello everyone,
During the past couple of years I have been playing around with Coppersmith's factorization factory approach for factoring SNFS numbers sharing a common rational polynomial, which was inspired by the factorization of several Mersenne numbers by this approach. Since I have not really found any publically available code to do this, I ended up writing some. I decided to make the code I have been using available, in case it is useful to anyone. It is available at GitHub, at https://github.com/ebranger/NFS_factory The implementation is fairly straightforward, taking as input gnfslasieve relations valid for the shared polynomial, using a batch GCD to remove most factors, and any remainder is tested in a double large prime fashion, using code I grabbed from msieve. Any found relations is then factored and outputted in a msieve format, to allow msieve to do the postprocessing. I have so far used the code to do about 250 SNFS220 factorizations. There are still some optimizations that can be done, but the speed is not too bad. On my system using 6 cores, a normal SNFS220 factorization takes about 12~14 days to finish. Using the factorization factory approach, batch factoring and postprocessing takes on the order of 24 days for numbers of that size. However, to this comes the amortized cost of finding the relations for the shared polynomial, which depends on the number of SNFS factorizations performed. In my case, the amortized cost is a bit under 2 days per number at the moment, for a comparable total time per factorization of about 46 days, which is still faster than the regular approach. I would also like to take this opportunity to thank all the people on mersenneforum. I have been lurking this forum for quite some time, and I have learnt a lot from your discussions. Hopefully I can contribute something back to you all! Erik 
20190826, 20:16  #2  
Nov 2003
2^{2}·5·373 Posts 
Quote:


20190826, 21:04  #3 
Dec 2008
you know...around...
28F_{16} Posts 
A certain Alberico Lepore might be interested in this...

20190830, 18:06  #4 
Jul 2018
19_{10} Posts 
Thank you for posting this!
I'd noticed your work in progress by finding the github page when researching the factorization factory idea, and later realizing you were behind a number of factorizations with shared polynomials on stdkmd.com. This project is probably going to be the final push I need to build and deploy msieve myself and (try to) finish off factoring 37w1 composites. 
20190831, 21:32  #5  
Oct 2018
2^{3}·3 Posts 
Quote:
The nearrepdigit project is really nice for the SNFS factorization factory approach, since there are typically hundreds of numbers sharing a rational polynomial. Right now I am working on clearing all numbers with a SNFSdifficulty of ~219222, which should keep me occupied for the forseeable futureā¦ I am also looking into if I can sieve more to use the same relation set to factor SNFS275 numbers. I still need to figure out good parameters for that, which is a challene since the factorization factory apporach has not been widely used. And I probably have to buy a new hard drive to store the ~100G or so additional relations needed 

20190902, 18:39  #6 
Jul 2018
19 Posts 
Correct, my factorizations have been done with CADONFS via SNFS or sometimes GNFS. I have not really been focused on optimizing NFS parameters, however; rather I've been working on trying to streamline and manage a pipeline of factoring jobs.
Mersenne Forum has been very helpful, pointing me in the right direction to the point that I can find my own algebraic polynomials and understand the factorization factory paper at a high level, if not the details. I wouldn't be surprised if CADO could be built and run reasonably on the Ubuntu Windows tools, but neither would I be shocked to learn that they don't; one of my earliest CADONFS jobs nearly failed because of some oddness in macOS, I think. That said I have saved most of my relations, so I'm curious to see if any of them can be reused or if I can adopt the factory approach going forward: clearing out 37w1 is going to be difficult verging on perhaps impossible. 
20190903, 08:58  #7  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{2}·13·113 Posts 
Quote:
I have been working through using the factorization factory attempting to use it for a constant algebraic polynomial(using deg 8 rather than 4 to keep the rational small). I have managed to produce relations and passed them to msieve, however, I didn't have enough. I also got a 11 error on about 10% of the relations. I am thinking of switching sieving to the CADO siever as I am hoping it will be more resilient with very small numbers. 

20190903, 09:57  #8  
Oct 2018
2^{3}·3 Posts 
Quote:
Quote:
Also, when changing the polynomial degree away from the optimal one, a bit more relations seems to be needed to finish, even if all other parameters are the same. The code reads the relations in gnfslasieve/msieve format, so if CADO relations are provided some new input/output functions would have to be written. Reading the relations should not be that hard, since manly the (a,b) values of the relations are needed, but outputting relations in CADO format will probably require more work. 

20190903, 13:59  #9  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
1011011110100_{2} Posts 
Quote:
CADO uses the same format for relations as the ggnfs siever. I would still use msieve for the postprocessing. 

20190903, 18:29  #10 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
13364_{8} Posts 
I have worked out the error. 7213133561 divided one of my rational relations. The hex for 72131335612^32=2918166265 was what was output to file.
It looks like the current solution is to reduce the large prime bound to 32(which makes sense anyway in my case). Last fiddled with by henryzz on 20190903 at 18:30 
20190903, 19:38  #11  
Oct 2018
2^{3}×3 Posts 
Quote:
And thank you for the clarification about the CADO relation format, I was under the impression that the differences were more significant, and that some conversion needed to take place to make gnfslasieve relations into CADO ones. But if they are the same then it should be no problem to take CADO relations as input. You are also correct in that factors less than 1000 are not printed, since I assume msieve will handle that. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factorization of RSA180  Robert Holmes  Factoring  19  20101108 18:46 
Factorization of 7,254+  dleclair  NFSNET Discussion  1  20060321 05:11 
Factorization of 11,212+  Wacky  NFSNET Discussion  1  20060320 23:43 
Factorization of 5,307  Jeff Gilchrist  NFSNET Discussion  7  20050223 19:46 
Factorization of M(738)  McBryce  Factoring  2  20030919 19:32 