mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2003-08-10, 02:31   #1
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5×7×167 Posts
Default 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/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
rogue is offline   Reply With Quote
Old 2003-08-11, 16:26   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2·5,693 Posts
Default

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
ewmayer is offline   Reply With Quote
Old 2003-08-11, 17:40   #3
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5×7×167 Posts
Default

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...
rogue is offline   Reply With Quote
Old 2003-08-11, 17:50   #4
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

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 is offline   Reply With Quote
Old 2003-08-11, 17:53   #5
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

Quote:
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?
smh is offline   Reply With Quote
Old 2003-08-11, 20:14   #6
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26×5 Posts
Default

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.
ColdFury is offline   Reply With Quote
Old 2003-12-11, 18:28   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2×5,693 Posts
Default

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
ewmayer is offline   Reply With Quote
Old 2003-12-12, 08:21   #8
BotXXX
 
BotXXX's Avatar
 
Aug 2003
Europe

110000102 Posts
Default

Quote:
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 ;)

these are available precompiled for Windows and Linux ;) up to 100-digits, but 120 is also possible with the right hardware.
BotXXX is offline   Reply With Quote
Old 2003-12-12, 14:04   #9
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

133258 Posts
Default

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
rogue is offline   Reply With Quote
Old 2003-12-12, 14:30   #10
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

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:
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
smh is offline   Reply With Quote
Old 2003-12-12, 14:57   #11
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2×32×131 Posts
Default

Quote:
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.
wblipp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Links to factoring programs smh Factoring 71 2019-02-21 22:33
Links to Factoring Projects rogue Factoring 20 2014-11-19 01:08
factoring programs henryzz Factoring 6 2007-09-19 13:47
looking for Fermat factoring programs ixfd64 Factoring 1 2005-09-08 12:13
any good GNFS factoring programs? ixfd64 Factoring 1 2004-04-27 09:41

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

Wed Aug 5 20:08:59 UTC 2020 up 19 days, 15:55, 2 users, load averages: 1.48, 1.60, 1.57

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.