20071122, 16:01  #1 
"Mark"
Apr 2003
Between here and the
2·3,217 Posts 
New program to fully factor with GMPECM
I attached a standalone program that will fully factor an input number with GMPECM.
Compile with the command "gcc factor.c primes.c O3 lgmp o factor" and put in the same directory with the GMPECM executable. Here are a couple of examples of how it looks: Code:
./factor 9257275928475984752938457293845723948573248957234958724952345234523433 Performing trial division to 100000000 42101 * 2163401 Starting P+1, 3 attempts for B1=300 Starting P1, 0 attempts for B1=300 Starting ECM, 8 attempts for B1=300 Starting P+1, 3 attempts for B1=2000 Starting P1, 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) Code:
./factor 294572495729457294857239485723948572358972358972340589732450923847504589735897245432555 Performing trial division to 100000000 3 * 3 * 5 Starting P+1, 3 attempts for B1=300 Starting P1, 0 attempts for B1=300 Starting ECM, 8 attempts for B1=300 Starting P+1, 3 attempts for B1=2000 Starting P1, 1 attempts for B1=2000 Starting ECM, 30 attempts for B1=2000 Starting P+1, 3 attempts for B1=11000 Starting P1, 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) 
20071122, 20:03  #2 
Sep 2005
Berlin
2×3×11 Posts 
Really a good idea to use gmpecm for automatically factoring :)
I tried to build it: The first compilation produced the following: Code:
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) 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... Last fiddled with by Yamato on 20071122 at 20:10 
20071122, 20:46  #3 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
31×191 Posts 
could someone post a win32 executable please
brill idea i was just about to suggest this myself 
20071122, 21:13  #4  
"Mark"
Apr 2003
Between here and the
2·3,217 Posts 
Quote:
Quote:
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 GMPECM, so it cannot handle expressions at this time. Mark Last fiddled with by rogue on 20071122 at 21:13 

20071122, 23:19  #5  
Sep 2005
Berlin
102_{8} Posts 
Quote:
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). 

20071123, 00:35  #6  
"Mark"
Apr 2003
Between here and the
2×3,217 Posts 
Quote:
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. Last fiddled with by rogue on 20071123 at 00:36 

20071123, 01:23  #7 
"Jason Goatcher"
Mar 2005
3·7·167 Posts 
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 trialanderror 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.) Last fiddled with by jasong on 20071123 at 01:24 Reason: added comment at end 
20071123, 02:17  #8  
"Mark"
Apr 2003
Between here and the
2×3,217 Posts 
Quote:
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 GMPECM 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 GMPECM. 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 email is rogue (at) wi.rr.com for anyone who wants to collaborate on this. 

20071123, 05:35  #9 
"Jason Goatcher"
Mar 2005
110110110011_{2} Posts 
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

20071123, 10:25  #10  
"Mark"
Apr 2003
Between here and the
2×3,217 Posts 
Quote:
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 P1 for higher B1 values than ECM. In other words, do P1 for 3e6 before ECM at 1e6 (or 25e4 possibly). This would be similar to p1depthoverecm setting for the ECMNet server. 

20071123, 21:05  #11 
Tribal Bullet
Oct 2004
3·1,181 Posts 
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).

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
My factor program...  Xyzzy  Programming  18  20140726 15:42 
C program to factor using GMPECM and msieve  lazy  GMPECM  6  20070616 18:12 
Program to factor F14  dsouza123  Programming  79  20060123 11:42 
Where I find the best program to it factor keys? I use AMD.  chrow  Factoring  5  20040219 10:15 
New program to test a single factor  dsouza123  Programming  6  20040113 03:53 