Links to Factoring Programs

[rogue]

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/P-1/P+1:
GMP-ECM (for any CPU that supports GMP) http://groups.yahoo.com/group/primen...grams/GMP-ECM/

For ECM/SIQS
Java ECM (java applet) http://www.alpertron.com.ar/ECM.HTM

For ECM/P-1/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.parigp-home.de/

For QS:
mpqs4linux (x86 only) ftp://ftp.math.uni-bonn.de/people/franke/mpqs4linux
LiDIA (for any CPU that supports GMP) www.informatik.tu-darmstadt.de/TI/LiDIA/
PPMPQS (x86 only) http://www.asahi-net.or.jp/~KC2H-MSM/cn/
PPSIQS (x86 only) http://www.asahi-net.or.jp/~KC2H-MSM/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 non-x86 CPU, I would like to hear from you.

GMP-ECM is faster on PPC (and more flexible) than the AltiVec enhanced one available from Apple, so I use GMP-ECM. My apologies to Richard Crandall.

I hope some of you find this useful.

--Mark

[ewmayer]

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

[rogue]

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...

[smh]

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.

[smh]

Some of you probably know, that building mpqs4linux is no small task.

I've taken a look at it before but since i know almost nothing about Linux i gave up.

Any chance that this can be compiled for windows?

[ColdFury]

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.

[ewmayer]

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 CPU-day on a GHz-class Pentium CPU). Jens Franke's documentation mentions 80 digits, but it would be nice if there were a simple-to-use MPQS or GNFS code that would allow one to factor up to (say) 100 digits with a not-egregious amount of CPU time.

Thanks,
-Ernst

[BotXXX]

Originally posted by ewmayer
Does anyone have a precompiled version of an efficient MPQS code for x86/Windows?

Look in the first post of this topic ;)

PPMPQS (x86 only) http://www.asahi-net.or.jp/~KC2H-MSM/cn/
PPSIQS (x86 only) http://www.asahi-net.or.jp/~KC2H-MSM/cn/

these are available precompiled for Windows and Linux ;) up to 100-digits, but 120 is also possible with the right hardware.

[rogue]

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 non-x86 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

[smh]

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.

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.

I would be very interested in this version.

FWIW, i recentely did a C143 using Ubasic's NFSX in about 12 days on a P3 733

[wblipp]

Originally posted by smh
FWIW, i recentely did a C143 using Ubasic's NFSX in about 12 days on a P3 733

That's interesting to me because ElevenSmooth has a C149 that is presently testing for 50 digit factors. Do I recall correctly, though, that this works with the Special Number Field Sieve, not the General? I think that means we would need to find a polynomial for the C149 - and I don't know how the time would scale from C143 to C149, either.