20041012, 16:54  #1 
"Mike"
Aug 2002
1D87_{16} Posts 
Perpetual ECM factoring challenge thread...
The idea for this post came from the "odd perfect numbers" thread...
I run GIMPS most of the time, but I'm very interested in running ECM for interesting problems... If we get enough people together we could probably put a serious dent into a problem in a matter of a few days or a week or so... By running mprime in the background I am not losing any clock cycles, and recently I've found that mprime's "pause while running" option lets me run ECM with no noticeable slowdown... So, the rules: The factoring challenge you post needs to be somewhat interesting... Some background about the problem and/or links to relevant pages would be fun and educational... I look at this as not just a chance to work on factoring, but a chance to learn... Too often I remain absorbed in my own little world and maybe exposure to other work that is going on will be beneficial... The challenge you post has to be reasonable... I'm sure there are lots of things out there that would take eons to calculate, so let's just focus on ones that are doable in a reasonable amount of time... With one computer, 10,000 curves might seem impossible, but spread that over a few boxes and it suddenly becomes achievable... I expect this thread to be fairly high volume, what with all the status reports and minor questions... I hope that this does not detract from its usefulness... Also, consider that most people who read this forum are not mathematicians... Many people will gladly contribute clock cycles if it is somewhat easy... IOW, maybe help a newbie get ECM set up, or post the exact command line to get the work started, or offer help with theory... I know that I've wanted to run some of the more esoteric stuff, like ECM, and without akruppa and philmoore's help I would never have figured it out... I think one of the major advantages of GIMPS is you can just click a few buttons and get running... Something else to consider is many people are willing to jump on and help, but they do not want to commit to a problem that is going to take weeks or months... Look at all the people who sign up for GIMPS and never finish even one test... With this challenge, a person could do a few hours or a few days worth of work and it would be meaningful... I'm not saying that we need to make all this idiot proof... But making it easier is always a good thing, right? Once we get the newbie past the initial hurdle who knows how far his or her interest might go? I realize that one can just hop on an ECM server and get work automatically, but that kind of setup assumes that the problem is something that you are aware of and are interested in... IOW, if you know what you are doing, then this thread might not seem interesting to you... Think of all the people who run GIMPS full time, who might be willing to donate a week or a few days of time for an interesting problem... I don't see this as a full time deal for most people, but who knows, maybe once they try it they might like it... If this is a stupid idea, please let me know... Suggestions and comments are welcome as always... I have a computer standing by, waiting for work... Who will join me? 
20041012, 17:38  #2 
"Mark"
Apr 2003
Between here and the
2^{3}×3×241 Posts 
Start at http://www.loria.fr/~zimmerma/records/ecmnet.html. I have done curves for Paul's project and am currently working on Sander Hoogendoorn's Home Prime search while testing the new ECMNet Client/Server code.

20041012, 17:42  #3  
Banned
"Luigi"
Aug 2002
Team Italia
1001010010011_{2} Posts 
Quote:
What if we help GIMPS ECM pages, running curves on those numbers? 2^{1061}1 seems a good candidate... Luigi P.S. What does IOW mean? Last fiddled with by ET_ on 20041012 at 17:43 

20041012, 18:22  #4 
Jun 2004
UK
213_{8} Posts 
This is exactly what I've been looking for. GIMPS is cool but it's rare you feel like you're making any sort of worthwhile contribution.
As the smallest M unfactored M1061 definitely seems like a worthwhile project. At this point the people who better know what they're doing usually say "I'll run some curves" but it'd be nice to have some more information. Looking at http://www.mersenne.org/ecmm.htm I see a table with B1=44,000,000. Does this mean I should run "ecm 44000000 < M1061"? I understand ECM picks random sigmas and each different sigma gives different results and therefore multiple people can work on the same exponent. Does this mean that it's near impossible for two people to be doing the same and therefore redundant work? Is there any information I need to store to record what work others have done? Is it necessary to have lowm.txt and lowp.txt in the directory? Once the program is running do I just wait until it says it's found a factor and if i get bored stop it? If i do get bored and decide to stop it has my work been pointless or can you add my curves to the list? It'd also be nice if someone could give some idea of what output to expect. For example how long does a curve take? Will the program tell me when I've completed a curve? When I report back do I just say "I did N curves"? Once we've altogether done 19300 curves do we just declare that M1061 has no 50 digit factor or do we just think it probably doesn't and then we move on to looking for 55 digits? Sorry for the burst of questions but if at least some get answered I'll be a happier bunny. 
20041012, 19:02  #5  
Nov 2003
1110100010110_{2} Posts 
Quote:
the Web page. How long a curve takes depends on the step limits and the machine. The code tells you when you have completed a curve. When you have done some curves, report it to George Woltman. After 19300 curves, the chance that we will have found a 50 digit factor, IF IT EXISTS, is (11/e). We should then just move on to 55 or 60 digits. I have a wrapper for Windows. It asks for the input file name, the step limit, number of curves to run, and the output file name. It is useful because the "ecmloop.bat" batch file goes to sleep under windows unless the window it is in HAS THE FOCUS. I'd also like to see a strong effort on P1123. 

20041012, 19:35  #6  
"Phil"
Sep 2002
Tracktown, U.S.A.
1,117 Posts 
Quote:
2) Yes, unless you are running on a number like M1061 or P16384 (the 14th Fermat number) which has no known factors. 3) Yes. Under mprime or prime95, you specify the number of curves you want to run. I typically will run 500 curves on one number and then go on to another number by editing command lines in the "worktodo" file. 4) As long as you know how many curves you have run, go ahead and report them. 5) Depends. Prime95 tells when you have completed a curve. I believe I have seen a posting that tells how to get mprime to tell you. 6) N curves on (say) M1061 with B1=44000000, for example. 7) You can do either. For numbers to be attacked later by the Number Field Sieve, there is generally a desired ECM factoring level to reach before starting NFS. 

20041012, 19:37  #7  
Bamboozled!
May 2003
Down not across
10,069 Posts 
Quote:
It has 311 digits, all of which are "1", and has no known factors. It is the current frontrunner candidate for the first SNFS factorization of an integer of > 1024 bits. It has a pleasing resonance with the first SNFS factorization of a > 768bit integer. That one was R211 which also had no known factors before The Cabal cracked it a few years ago. R311 has been swept to 50digit factors already and a small team has started searching with parameters optimized for finding 53, 55 and 60 digits. It should be swept to at least 55 digits, and preferably 60 digits, before the SNFS factorization is started. I intend to put together a page which summarizes known effort on R311. If there is sufficient interest here, that page may appear earlier than it would otherwise do. Paul 

20041012, 19:46  #8  
Nov 2003
1D16_{16} Posts 
Quote:
code changes; many things done now in single precision would require double precision, just to cite one problem. 

20041012, 22:25  #9 
Jul 2004
Potsdam, Germany
33F_{16} Posts 
AFAIK, it's wise to use SSE2enabled CPUs to work on 1 numbers, whereas others more or less don't care and thus basically better do +1 numbers, as the SSE2 routines haven't been ported to P numbers yet. Is this correct?
Of course, you can do M<2*n> to get factors for P<n>, but I'm not sure if this is that efficient, assuming that M<n> is no additional candidate for ECMing... If said is true, maybe a partitioning to different numbers would increase overall throughput. 
20041013, 07:23  #10 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
The new DWT library by George can handle a*2^n+c for small a,c with SSE2 for all kinds of FFT lenghts. It will do away with having to work on 2^2n1 to get SSE2 and splitting residues before feeding them to gmpecm. I don't know if there'll be a nonSSE2 implementation. If there's not, the situation will completely turn around: 2^n+1 numbers will preferably be done on SSE2 machines thanks to more FFT lengths, and 2^n1 numbers should then be left to nonSSE2.
Alex 
20041013, 07:48  #11  
Bamboozled!
May 2003
Down not across
10,069 Posts 
Quote:
Many of these things have already been identified. Some of them have already been addressed in some versions of the software. For instance, although the CWI tool set is limited at present to 30bit large primes, Jens Franke's siever allows them to be >32 bits. IIRC, the rsa576 factorization used LPB=2^33 except where the CWI siever was used when it was 2^30. Noone believes it will be easy. A goodly number believes it is possible within a year or two. Paul 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Perpetual benchmark thread...  Xyzzy  Hardware  813  20200507 17:00 
Perpetual I'm pi**ed off thread  rogue  Soap Box  19  20091028 19:17 
Perpetual "interesting video" thread...  Xyzzy  Lounge  9  20061224 20:06 
Perpetual autostereogram thread...  Xyzzy  Lounge  10  20060928 00:36 
Regards RSA factoring challenge  koders333  Factoring  5  20060328 13:50 