New program to fully factor with GMP-ECM

[rogue]

I attached a stand-alone program that will fully factor an input number with GMP-ECM.

Compile with the command "gcc factor.c primes.c -O3 -lgmp -o factor" and put in the same directory with the GMP-ECM executable.

Here are a couple of examples of how it looks:

./factor 9257275928475984752938457293845723948573248957234958724952345234523433
Performing trial division to 100000000
42101 * 2163401
Starting P+1, 3 attempts for B1=300
Starting P-1, 0 attempts for B1=300
Starting ECM, 8 attempts for B1=300
Starting P+1, 3 attempts for B1=2000
Starting P-1, 1 attempts for B1=2000
Starting ECM, 30 attempts for B1=2000
method=ecm, B1=2000  * 174543688939 (prp)
 * 582303795308186678526593123206720017741906336247 (prp)
The factorization for
9257275928475984752938457293845723948573248957234958724952345234523433
is:
   42101 (prime)
 * 2163401 (prime)
 * 174543688939 (prp)
 * 582303795308186678526593123206720017741906336247 (prp)

./factor 294572495729457294857239485723948572358972358972340589732450923847504589735897245432555
Performing trial division to 100000000
3 * 3 * 5
Starting P+1, 3 attempts for B1=300
Starting P-1, 0 attempts for B1=300
Starting ECM, 8 attempts for B1=300
Starting P+1, 3 attempts for B1=2000
Starting P-1, 1 attempts for B1=2000
Starting ECM, 30 attempts for B1=2000
Starting P+1, 3 attempts for B1=11000
Starting P-1, 1 attempts for B1=11000
Starting ECM, 74 attempts for B1=11000
method=ecm, B1=11000  * 20673647734703 (prp)
method=ecm, B1=11000  * 1145790266539004269 (prp)
 * 276348708948598769541402380201345326771795822745676797 (prp)
The factorization for
294572495729457294857239485723948572358972358972340589732450923847504589735897245432555
is:
   3 (prime)
 * 3 (prime)
 * 5 (prime)
 * 20673647734703 (prp)
 * 1145790266539004269 (prp)
 * 276348708948598769541402380201345326771795822745676797 (prp)

I have not included a means to skip lower B1 values, but that should be easy to do. Let me know if you find it useful and if you would like me to make any enhancements to it.

[Yamato]

Really a good idea to use gmp-ecm for automatically factoring :-)
I tried to build it: The first compilation produced the following:

factor.c: In function ‘main’:
factor.c:90: error: ‘SIGINT’ undeclared (first use in this function)
factor.c:90: error: (Each undeclared identifier is reported only once
factor.c:90: error: for each function it appears in.)
factor.c:91: error: ‘SIGQUIT’ undeclared (first use in this function)
factor.c:92: error: ‘SIGTERM’ undeclared (first use in this function)

After including "signal.h" in factor.c, the 'SIGQUIT' was still missing. So I omitted that line and the compiler was happy (where is the mistake?).

The program works well under Linux. But when I use MinGW to get an *.exe, die program produces an error message (that he can't find the command "."). Your program calls "./ecm(...)", but that doesn't work with Windows...

[henryzz]

could someone post a win32 executable please

brill idea i was just about to suggest this myself

[rogue]

Originally Posted by Yamato

Really a good idea to use gmp-ecm for automatically factoring :-)
I tried to build it: The first compilation produced the following:

factor.c: In function ‘main’:
factor.c:90: error: ‘SIGINT’ undeclared (first use in this function)
factor.c:90: error: (Each undeclared identifier is reported only once
factor.c:90: error: for each function it appears in.)
factor.c:91: error: ‘SIGQUIT’ undeclared (first use in this function)
factor.c:92: error: ‘SIGTERM’ undeclared (first use in this function)

After including "signal.h" in factor.c, the 'SIGQUIT' was still missing. So I omitted that line and the compiler was happy (where is the mistake?).

The program works well under Linux. But when I use MinGW to get an *.exe, die program produces an error message (that he can't find the command "."). Your program calls "./ecm(...)", but that doesn't work with Windows...

There is an #ifdef that defines the name of the executable to run. On Windows it should be "ecm", not "./ecm". I might be missing a condition. If you can determine what that condition is, let me know and I'll update the code. SIGQUIT should be in signal.h, but it won't cause any significant harm if it is missing. SIGTERM and SIGINT are more common signals than SIGQUIT.

Originally Posted by henryzz

could someone post a win32 executable please

This presumes you already have a win32 version of GMP-ECM. My program requires GMP, so it would have to be built with a static library.

BTW, have you tried to build GMP yourself? It would require MSYS or MinGW, but there are people in this group who could help.


Of note, my program has no expression parser, unlike GMP-ECM, so it cannot handle expressions at this time.

--Mark

[Yamato]

Originally Posted by henryzz

could someone post a win32 executable please

brill idea i was just about to suggest this myself

Here is a binary for win32: factor_ecm_win32.zip

Furthermore I have two questions:
1. Why trial division up to 10^8? I think it's quite enough to do that up to 10^6. The program would appear faster, otherwise starting it takes some seconds for the trial stage.
2. Is it possible to include a "quiet" option? That means only to print the factors (without additional information about the computation process).

[rogue]

Originally Posted by Yamato

Furthermore I have two questions:
1. Why trial division up to 10^8? I think it's quite enough to do that up to 10^6. The program would appear faster, otherwise starting it takes some seconds for the trial stage.
2. Is it possible to include a "quiet" option? That means only to print the factors (without additional information about the computation process).

1. I choose 10^8 to significantly reduce the likelihood of GMP-ECM returning a composite factor for small B1 values.

2. Yes. Until I do it, it should be easy for you to modify the code to reduce the amount of output. BTW, I think that the output is meaningful from the perspective that you can see where it is in the factorization.

[jasong]

I have a request to make, and it's only a request. I've tried to make small programs in the past and I know what a difficult trial-and-error process it can be.

There are guidelines to how many curves to do for certain numbers, for instance there's this page. These guidelines are for people who are just going to plug away with ecm until they give up or the numbers factored. I was wondering if your program could be set up to (1) skip lower digit levels upon user request, (2) be able to deal with the possibility that a digit level is only partially done, and (3) accept a number, probably a decimal, that tells it what proportion of the recommended curves are desired to be done.

It's only a request, but it would be very much appreciated.

YOU ROCK!!!

(Forget Hollywood. Open source programmers are MY heroes.)

[rogue]

Originally Posted by jasong

There are guidelines to how many curves to do for certain numbers, for instance there's this page. These guidelines are for people who are just going to plug away with ecm until they give up or the numbers factored. I was wondering if your program could be set up to (1) skip lower digit levels upon user request, (2) be able to deal with the possibility that a digit level is only partially done, and (3) accept a number, probably a decimal, that tells it what proportion of the recommended curves are desired to be done.

The number of curves that the program uses comes from GMP-ECM 6.1.1. The curve counts in that version are more refined than v6.0. I don't know if they have changed again with any minor revisions since 6.1.1.

1) Definitely a nice to have. It won't be too hard to do.
2) Harder to do and I don't state how many curves have been done for that B1 when the program is terminated. I'll think about it. It might require an ini file to manage the run.
3) The program only accepts numbers in decimal form, i.e. no expressions. Expression parsers can be nasty to write and I wouldn't want to write one from scratch. I suppose it might be possible to link in the expression parser from GMP-ECM and use it. I don't know what you mean by "proportion of the recommended curves".

I don't have any concrete plans for a new release at the moment. Some thoughts I have, some of which are based upon ideas in this thread, are:

1) Allow skipping of trial division (or set the limit).
2) Skip certain B1 levels.
3) Allow input from a file, thus allowing multiple factorizations for a run.
4) Outputting factorizations to a log file.
5) Using an ini file so that it could be stopped and restarted.
6) Using msieve under certain conditions to finish the factorization.

Of note, the point of the program is to provide a full factorization of the input, meaning that all factors are prime or PRP. Skipping (or lowering the limit of) trial division could lead to composite factors found by GMP-ECM. Skipping would only be suggested if the user know that all small factors have been removed.

Others are welcome to add their 2 cents or code improvements as they see fit. My e-mail is rogue (at) wi.rr.com for anyone who wants to collaborate on this.

[jasong]

Originally Posted by rogue

I don't know what you mean by "proportion of the recommended curves".

There's more to the quote than that. :) I'll explain with an example. Let's say we have a number we want to factor and we come up with some B1/B2 values that are stated to be optimal. Well, I've been told that those curves that are recommended are only appropriate if you're going to do ecm forever and only stop when you factor the number.(or give up) The proportion of the recommended curves number means the number I would multiply the recommended curves by to get a new number of curves to be done. I might want to give it the number .5, and every time it got to a new B1 value it would only do half the number of recommended curves

[rogue]

Originally Posted by jasong

There's more to the quote than that. :) I'll explain with an example. Let's say we have a number we want to factor and we come up with some B1/B2 values that are stated to be optimal. Well, I've been told that those curves that are recommended are only appropriate if you're going to do ecm forever and only stop when you factor the number.(or give up) The proportion of the recommended curves number means the number I would multiply the recommended curves by to get a new number of curves to be done. I might want to give it the number .5, and every time it got to a new B1 value it would only do half the number of recommended curves

But the point of my program is to fully factor the number. It sounds to me as if you want to do a percentage of curves for high values of B1 just to do some speculative runs of ECM in the hopes of finding a factor. I have no way of knowing when a user would want to give up. I also want to avoid doing any complicated math to calculate the correct value for B1 and the number of curves dynamically based upon the input. If someone following this thread has an interest in incorporating such code, go for it and send the improvements on to me for a future release.

Although, this gives me ideas for two more enhancements:
1) A command line option to set the max B1. In other words by using this option the program would stop after doing all curves at B1=3e6.
2) Run P-1 for higher B1 values than ECM. In other words, do P-1 for 3e6 before ECM at 1e6 (or 25e4 possibly). This would be similar to p-1depthoverecm setting for the ECMNet server.

[jasonp]

Originally Posted by rogue

I attached a stand-alone program that will fully factor an input number with GMP-ECM.

Since this seems to be getting some steam behind it, someone should add Pollard Rho before the other methods. Also, someone should add msieve in QS mode for small enough jobs (I'll volunteer to add that if nobody else will).