mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2004-10-12, 16:54   #1
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

1D8716 Posts
Default 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?
Xyzzy is offline   Reply With Quote
Old 2004-10-12, 17:38   #2
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

23×3×241 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2004-10-12, 17:42   #3
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

10010100100112 Posts
Default

Quote:
Originally Posted by Xyzzy
I have a computer standing by, waiting for work... Who will join me?
Here I am!

What if we help GIMPS ECM pages, running curves on those numbers?

21061-1 seems a good candidate...

Luigi

P.S. What does IOW mean?

Last fiddled with by ET_ on 2004-10-12 at 17:43
ET_ is offline   Reply With Quote
Old 2004-10-12, 18:22   #4
marc
 
marc's Avatar
 
Jun 2004
UK

2138 Posts
Default

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.
marc is offline   Reply With Quote
Old 2004-10-12, 19:02   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101000101102 Posts
Thumbs up

Quote:
Originally Posted by marc
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"?


{YES! Bob}

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?

{Yes. Until you try ~sqrt(p) curves where p is the factor, collisions will
be very rare. That's a LOT of curves}

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.
A fair effort has already been expended on M1061. You already gave
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 (1-1/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.
R.D. Silverman is offline   Reply With Quote
Old 2004-10-12, 19:35   #6
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

Quote:
Originally Posted by marc
1) Is there any information I need to store to record what work others have done?
2) Is it necessary to have lowm.txt and lowp.txt in the directory?
3) Once the program is running do I just wait until it says it's found a factor and if i get bored stop it?
4) If i do get bored and decide to stop it has my work been pointless or can you add my curves to the list?
5) For example how long does a curve take? Will the program tell me when I've completed a curve?
6) When I report back do I just say "I did N curves"?
7) 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?
1) No.
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.
philmoore is offline   Reply With Quote
Old 2004-10-12, 19:37   #7
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

10,069 Posts
Default

Quote:
Originally Posted by Bob Silverman
I'd also like to see a strong effort on P1123.
I would like to see a strong effort on R311, also known as 10,311-.c311, aka (10^311-1)/9.

It has 311 digits, all of which are "1", and has no known factors. It is the current front-runner candidate for the first SNFS factorization of an integer of > 1024 bits. It has a pleasing resonance with the first SNFS factorization of a > 768-bit 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 50-digit 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
xilman is offline   Reply With Quote
Old 2004-10-12, 19:46   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D1616 Posts
Default

Quote:
Originally Posted by xilman
I would like to see a strong effort on R311, also known as 10,311-.c311, aka (10^311-1)/9.

It has 311 digits, all of which are "1", and has no known factors. It is the current front-runner candidate for the first SNFS factorization of an integer of > 1024 bits. It has a pleasing resonance with the first SNFS factorization of a > 768-bit 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 50-digit 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
An SNFS on 1024 bits would be a major effort. It would require extensive
code changes; many things done now in single precision would require
double precision, just to cite one problem.
R.D. Silverman is offline   Reply With Quote
Old 2004-10-12, 22:25   #9
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

33F16 Posts
Question

AFAIK, it's wise to use SSE2-enabled 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.
Mystwalker is offline   Reply With Quote
Old 2004-10-13, 07:23   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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^2n-1 to get SSE2 and splitting residues before feeding them to gmp-ecm. I don't know if there'll be a non-SSE2 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^n-1 numbers should then be left to non-SSE2.

Alex
akruppa is offline   Reply With Quote
Old 2004-10-13, 07:48   #11
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

10,069 Posts
Default

Quote:
Originally Posted by Bob Silverman
An SNFS on 1024 bits would be a major effort. It would require extensive
code changes; many things done now in single precision would require
double precision, just to cite one problem.
Correct.

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 30-bit large primes, Jens Franke's siever allows them to be >32 bits. IIRC, the rsa-576 factorization used LPB=2^33 except where the CWI siever was used when it was 2^30.

No-one believes it will be easy. A goodly number believes it is possible within a year or two.

Paul
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Perpetual benchmark thread... Xyzzy Hardware 813 2020-05-07 17:00
Perpetual I'm pi**ed off thread rogue Soap Box 19 2009-10-28 19:17
Perpetual "interesting video" thread... Xyzzy Lounge 9 2006-12-24 20:06
Perpetual autostereogram thread... Xyzzy Lounge 10 2006-09-28 00:36
Regards RSA factoring challenge koders333 Factoring 5 2006-03-28 13:50

All times are UTC. The time now is 00:18.

Sat Jul 4 00:18:06 UTC 2020 up 100 days, 21:51, 1 user, load averages: 1.50, 1.49, 1.38

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.