mersenneforum.org New program to fully factor with GMP-ECM
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2007-11-22, 16:01   #1
rogue

"Mark"
Apr 2003
Between here and the

2×3×1,123 Posts
New program to fully factor with GMP-ECM

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:
Code:
./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)
Code:
./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.
Attached Files
 factor.zip (5.0 KB, 705 views)

 2007-11-22, 20:03 #2 Yamato     Sep 2005 Berlin 2×3×11 Posts Really a good idea to use gmp-ecm 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) 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... Last fiddled with by Yamato on 2007-11-22 at 20:10
 2007-11-22, 20:46 #3 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 7·857 Posts could someone post a win32 executable please brill idea i was just about to suggest this myself
2007-11-22, 21:13   #4
rogue

"Mark"
Apr 2003
Between here and the

673810 Posts

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

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

Last fiddled with by rogue on 2007-11-22 at 21:13

2007-11-22, 23:19   #5
Yamato

Sep 2005
Berlin

6610 Posts

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

2007-11-23, 00:35   #6
rogue

"Mark"
Apr 2003
Between here and the

2×3×1,123 Posts

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

Last fiddled with by rogue on 2007-11-23 at 00:36

 2007-11-23, 01:23 #7 jasong     "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 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.) Last fiddled with by jasong on 2007-11-23 at 01:24 Reason: added comment at end
2007-11-23, 02:17   #8
rogue

"Mark"
Apr 2003
Between here and the

2×3×1,123 Posts

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

2007-11-23, 05:35   #9
jasong

"Jason Goatcher"
Mar 2005

350710 Posts

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

2007-11-23, 10:25   #10
rogue

"Mark"
Apr 2003
Between here and the

2·3·1,123 Posts

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

2007-11-23, 21:05   #11
jasonp
Tribal Bullet

Oct 2004

3×7×132 Posts

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

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy Programming 18 2014-07-26 15:42 lazy GMP-ECM 6 2007-06-16 18:12 dsouza123 Programming 79 2006-01-23 11:42 chrow Factoring 5 2004-02-19 10:15 dsouza123 Programming 6 2004-01-13 03:53

All times are UTC. The time now is 05:52.

Fri Oct 7 05:52:42 UTC 2022 up 50 days, 3:21, 0 users, load averages: 0.87, 0.99, 1.04

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔