20030810, 02:31  #1 
"Mark"
Apr 2003
Between here and the
17×347 Posts 
Links to Factoring Programs
I thought it would be of interest to readers of this forum to post links to the available factoring programs (and source if publicly available) along with the CPUs that it can be run on. Not all of us use (or desire to use) x86s, so it is nice to know what can run on other CPUs.
Let me start with what I can think of. For ECM/P1/P+1: GMPECM (for any CPU that supports GMP) http://groups.yahoo.com/group/primen...grams/GMPECM/ For ECM/SIQS Java ECM (java applet) http://www.alpertron.com.ar/ECM.HTM For ECM/P1/Pollard Rho: AltiVec MP (PPC with AltiVec only) http://developer.apple.com/hardware/...ecisionsam.sit For ECM/QS: PARI (for any CPU that supports GMP) www.parigphome.de/ For QS: mpqs4linux (x86 only) ftp://ftp.math.unibonn.de/people/franke/mpqs4linux LiDIA (for any CPU that supports GMP) www.informatik.tudarmstadt.de/TI/LiDIA/ PPMPQS (x86 only) http://www.asahinet.or.jp/~KC2HMSM/cn/ PPSIQS (x86 only) http://www.asahinet.or.jp/~KC2HMSM/cn/ I purposefully did not include some implementations that I found that are not intended for factoring large numbers. You're free to reply with links to those implementations if you think they are useful. LiDIA crashes on me whenever I use it. which is too bad because it appears to have an decent QS implementation. PARI is painfully slow so I avoid it. I tried building mpqs4linux on PPC, but I ran into a problem with a few routines written in x86 asm. Some I could code in C and some could be replaced with calls to GMP functions. But some x86 routines are not documented as to what they do and as I don't know much about x86 asm, I couldn't figure out how to replace them CPU agnostic. If someone has compiled mpqs4linux and run it successfully on a nonx86 CPU, I would like to hear from you. GMPECM is faster on PPC (and more flexible) than the AltiVec enhanced one available from Apple, so I use GMPECM. My apologies to Richard Crandall. I hope some of you find this useful. Mark 
20030811, 16:26  #2 
∂^{2}ω=0
Sep 2002
República de California
2·13·443 Posts 
Thanks for this compilation, Mark  I suggest you make this master list sticky, so it can be updated on an ongoing basis.
Another suggestion: implement a simply way of ranking the programs, for cases where there is more than one implementation available. For instance, PARI's interface is nice, but its speed generally sucks, so it could have a high rank for usability, but a low rank for speed. Cheers, Ernst 
20030811, 17:40  #3 
"Mark"
Apr 2003
Between here and the
17×347 Posts 
According to this http://groups.yahoo.com/group/primen.../message/10183, mpqs4linux is faster than PPSIQS (and probably PPMPQS).
Some of you probably know, that building mpqs4linux is no small task. It relies on other third party packages to generate some of the C code. In my experience with it, which is limited, I had to edit a number of files to get everything to generate, compile, and link correctly. Building mpqs4linux is not for the faint of heart, but provides great benefit if you can do it. Unfortunately for me, it was all for nought... 
20030811, 17:50  #4 
"Sander"
Oct 2002
52.345322,5.52471
29·41 Posts 
Jens Franke also wrote a NFS4Linux, but i can't seem to find it at the moment.
There's als a UBasic version of the SNFS called NFSX which is quite powerful for numbers of the right form (MUCH faster then ppsiqs or ppmpqs). It can be found here: ftp://rkmath.rikkyo.ac.jp./pub/ubtest/ It's a bit more complicated then putting a number in a text file and run it, but once you know how to set the right parameters it's not that hard either. I changed my version slightely so it saves the factorizations to an output file. 
20030811, 17:53  #5  
"Sander"
Oct 2002
52.345322,5.52471
29·41 Posts 
Quote:
Any chance that this can be compiled for windows? 

20030811, 20:14  #6 
Aug 2002
140_{16} Posts 
http://www.nd.edu/~cmonico/ggnfs/index.html is where Chris Monico is working on an open source inplementation of the GNFS. It's pretty slow right now, but constantly improving.

20031211, 18:28  #7 
∂^{2}ω=0
Sep 2002
República de California
2×13×443 Posts 
Does anyone have a precompiled version of an efficient MPQS code for x86/Windows? It would be nice if people wanting to use such a program don't each have to go through the hassle of building it themselves. (Along those lines, a prebuilt version for x86/linux would be nice, too.)
Also, what is the approximate upper limit of factoring size for these publicly available MPQS codes? (Say, in on the order of one CPUday on a GHzclass Pentium CPU). Jens Franke's documentation mentions 80 digits, but it would be nice if there were a simpletouse MPQS or GNFS code that would allow one to factor up to (say) 100 digits with a notegregious amount of CPU time. Thanks, Ernst 
20031212, 08:21  #8  
Aug 2003
Europe
2×97 Posts 
Quote:
Quote:


20031212, 14:04  #9 
"Mark"
Apr 2003
Between here and the
17·347 Posts 
mpqs4linux can handle over 100 digits as well and is supposedly faster than PPMPQS and PPSIQS, although I have never benchmarked them.
mpqs4linux has two factoring programs included. One is pmpqs, which is for composites under 80 digits, the other is ppmpqs (or parallel pmpqs) for composites over 80 digits. The largest number factored with ppmpqs is 127 digits. For those of you interested, mpqs4linux can be compiled on nonx86 CPUs with a little effort. I know because I've compiled it on PPC. I have tested pmpqs and it does work, but I haven't done any timings compared to x86. As for ppmpqs, I haven't tested it yet because I don't have the time. I expect it would take many days to verify if it runs correctly in PPC. When I get my G5 (sometime next year I hope), it should be easier for me to test ppmpqs on PPC. My dream (and a far away dream at that) is to vectorize (with AltiVec) the sieving and scheduling code in mpqs4linux. I have compiled and run pmpqs and ppmpqs on x86 using cygwin under Windows. I don't know if I can legally send anyone precompiled binaries otherwise I would offer to do so. Mark 
20031212, 14:30  #10  
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts 
I never use PPMPQS.EXE anymore since PPSIQS.EXE was faster on all numbers i tried.
105 digits should take about 10 days on a 2,5GHz P4. I know Tom Hill has done quite a few partition numbers upto 110 digits. Quote:
FWIW, i recentely did a C143 using Ubasic's NFSX in about 12 days on a P3 733 

20031212, 14:57  #11  
"William"
May 2003
New Haven
2×3^{2}×131 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Links to factoring programs  smh  Factoring  71  20190221 22:33 
Links to Factoring Projects  rogue  Factoring  20  20141119 01:08 
factoring programs  henryzz  Factoring  6  20070919 13:47 
looking for Fermat factoring programs  ixfd64  Factoring  1  20050908 12:13 
any good GNFS factoring programs?  ixfd64  Factoring  1  20040427 09:41 