mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2016-07-09, 09:24   #1
yoyo
 
yoyo's Avatar
 
Oct 2006
Berlin, Germany

23×7×11 Posts
Question larger B1 for GMP-ECM in yoyo@home

Hello,

I want to expand the GMP-ECM range which is handled in yoyo@home.
Do you think this is usefull?
The current range is: http://www.rechenkraft.net/wiki/inde...%40home_en#ECM

I currently perform some tests for composite length between c100-c350 and B1= 290e7, 760e7 and 25e9 to get the runtimes and memory requirements.

Do you thing this composite range is ok?

Out of this I derive forumlas to predict runtime & memory.

I think to sent it to the minions I have to limit the memory with -maxmem 12000 to 12 GB to get enough minions. Minions who have at least 16GB.

Opinions?

yoyo
yoyo is offline   Reply With Quote
Old 2016-07-09, 15:06   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

246768 Posts
Default

Quote:
Originally Posted by yoyo View Post
Hello,

I want to expand the GMP-ECM range which is handled in yoyo@home.
Do you think this is usefull?
The current range is: http://www.rechenkraft.net/wiki/inde...%40home_en#ECM

I currently perform some tests for composite length between c100-c350 and B1= 290e7, 760e7 and 25e9 to get the runtimes and memory requirements.

Do you thing this composite range is ok?

Out of this I derive forumlas to predict runtime & memory.

I think to sent it to the minions I have to limit the memory with -maxmem 12000 to 12 GB to get enough minions. Minions who have at least 16GB.

Opinions?

yoyo
First the maxmem figure, as that's the easiest. On my machines I tend to restrict it to 1000 or so because I run one client per core and I like other processes to get their share. If you run your clients multicore, or could set up your client software to do so, you may wish to choose -maxmem to be much less than 12G.

The other ranges are trickier, perhaps. Here's an analysis based on the well-known rules of thumb.

B1=25G is optimal for finding 80 digit factors. It does not really make sense for anything under 240 digits as those would best be done by GNFS anyway. Remember that the world record GNFS has only 232 digits ...

The other two are appropriate for 70 and 75 digits respectively. The GNFS cut-off is thrice that, so 210 and 225 digits respectively.

TL;DR I personally wouldn't run at any of the higher ranges. You might justify 2.9G for numbers > 200 digits or so.

For SNFS-able numbers the analysis is even gloomier. Multiply the digit counts by 1.5 to reach 315, 338 and 360 digits respectively before they are worth doing by ECM rather than SNFS.

Sorry if this is coming over as negative. I regard your project very highly indeed and I'm very grateful for the factors it finds (another only a couple of days ago)
and for the pre-testing necessary before committing resources to GNFS.

Paul

Last fiddled with by xilman on 2016-07-09 at 15:08 Reason: Fix parenthesis & typ
xilman is offline   Reply With Quote
Old 2016-07-09, 21:32   #3
yoyo
 
yoyo's Avatar
 
Oct 2006
Berlin, Germany

61610 Posts
Default

Thanks.
Main result of my tests currently will be functions to predict memory and runtime based on composite length for a given B1.
yoyo is offline   Reply With Quote
Old 2016-07-09, 22:24   #4
cgy606
 
Feb 2012

6310 Posts
Default

Quote:
Originally Posted by yoyo View Post
Thanks.
Main result of my tests currently will be functions to predict memory and runtime based on composite length for a given B1.
My understanding is that memory should be more dependent on the value of B2 and the length of the composite. The dependency between B1 and memory usage is pretty constant for various composite lengths...
cgy606 is offline   Reply With Quote
Old 2016-07-10, 06:13   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×13×137 Posts
Default

Quote:
Originally Posted by cgy606 View Post
My understanding is that memory should be more dependent on the value of B2 and the length of the composite. The dependency between B1 and memory usage is pretty constant for various composite lengths...
True, but by default the B2 value is dependent on the B1 value, so B1 is a good proxy for B2.
xilman is offline   Reply With Quote
Old 2016-07-13, 01:24   #6
swellman
 
swellman's Avatar
 
Jun 2012

23×3×53 Posts
Default

I've thought about this issue though of course I am only a hobbyist. It seems like two questions are being considered:

- can it be done?
- should it be done?

The first question of "can it be done" will be answered by yoyo's investigations. What are the performance requirements of an individual contributor's machine, and are there enough such users in the BOINC world to make the move to higher ECM levels feasible? If some % of current users can match these higher system requirements, yoyo will presumably need to adjust the credit system to make t70+ desirable to those users. Looking forward to yoyo's results, but I will be surprised if t80 is deemed practical even in a BOINC environment.

The second question of "should it be done" is discussed in xilman's excellent analysis. I will add that there are occasions where a number is too long/difficult for NFS attacks, but could possibly be at least partially factored with ECM methods. A C250 with SNFS difficulty of 320 is unlikely to be split by NFS in the next decade, but if one should find a p73 factor with ECM it suddenly becomes a very simple GNFS job. A few such big ECM factors have been found in the Cunningham project.

Guess it comes down to optimizing cycles used versus satisfying user (im)patience with Moore's law...
swellman is offline   Reply With Quote
Old 2016-07-13, 06:37   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1068610 Posts
Default

Quote:
Originally Posted by swellman View Post
The second question of "should it be done" is discussed in xilman's excellent analysis. I will add that there are occasions where a number is too long/difficult for NFS attacks, but could possibly be at least partially factored with ECM methods. A C250 with SNFS difficulty of 320 is unlikely to be split by NFS in the next decade, but if one should find a p73 factor with ECM it suddenly becomes a very simple GNFS job. A few such big ECM factors have been found in the Cunningham project.
I agree with that analysis, but a p53 might also be found by an ECM curve of the same cost in computation and memory usage as one optimized for a p73. It would be more efficiently found by running curves at a lower B1 value.

I'm not doubting that finding >p70 factors would be useful. I'm only suggesting that one shouldn't go looking for them unless one is already fairly sure that nothing smaller is to be found.

FWIW, I've been following a similar strategy with some c180-C200 GCW candidates. I'm looking for p50-p55 factors and a cofactor which is in GNFS range. However, I'm not (yet) looking for larger factors because there is a fair chance that others in the p50-p55 range are to be found.

In the end the decisions are whether yoyo should provide the service and whether those who queue work make use of it. My view is that the latter group should decline unless they have good reasons; my posts are an attempt to guide their reasoning.
xilman is offline   Reply With Quote
Old 2016-07-13, 12:53   #8
yoyo
 
yoyo's Avatar
 
Oct 2006
Berlin, Germany

23×7×11 Posts
Default

I have much less experience on ecm than you.
I assume that authors who put composites into the ecm queue first tries lower B1 after they move to large B1.

But anyway, I have more questions regarding gmp-ecm.
1) Is there a way to run only phase1, save the result and continue with phase2 on a different host?

2) Is there a way to stop phase1 after some time/iterations, and continue on a different host? At least with -chkpnt/resume file the state can be saved and resumed from it.

yoyo

Last fiddled with by yoyo on 2016-07-13 at 13:05
yoyo is offline   Reply With Quote
Old 2016-07-13, 13:28   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·5·587 Posts
Default

If anyone has looked at fivemack's Bayesian analysis of the number of curves needed, it seems quite common with smaller numbers that it is worth doing a small number of curves at each level rather than doing a full t50 etc. This means that instead of doing a t50 with 43e6 you would do some at 43e6, 11e7 26e7 and maybe 85e7(the largest curves haven't been fully added yet)
This will probably be even more true for larger numbers it is just that the larger curves aren't fully supported by his script yet.
henryzz is offline   Reply With Quote
Old 2016-07-13, 13:48   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×13×137 Posts
Default

Quote:
Originally Posted by yoyo View Post
I have much less experience on ecm than you.
I assume that authors who put composites into the ecm queue first tries lower B1 after they move to large B1.

But anyway, I have more questions regarding gmp-ecm.
1) Is there a way to run only phase1, save the result and continue with phase2 on a different host?

2) Is there a way to stop phase1 after some time/iterations, and continue on a different host? At least with -chkpnt/resume file the state can be saved and resumed from it.

yoyo
1) yes. I do it all the time, running phase1 on a GPU and then splitting the resulting save files over several cores, not necessarily all on the same host.

2) Yes, but ...

You can stop phase 1 after completing the complete B1. Not what you mean but it is, technically, a solution to your question as asked. Likewise, checkpoint files (equivalent to stopping, temporarily, at a specific number of iterations) can be continued elsewhere.

Perhaps you should ask ecm-dev whether a more flexible interrupt capability (for both phases) can be implemented because it would help large-scale distributed computations such as your and the ECMNet client/server network. I would give public support to your request.

Note that it is already straightforward to distribute phase 2 over multiple cores. You may wish to consider that in your project.
xilman is offline   Reply With Quote
Old 2016-07-13, 15:04   #11
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

587010 Posts
Default

I believe it is already possible to continue a stage 1 from a save file. Interrupting should hopefully be addable I would imagine.

Back to my previous post:
Ecming a gnfs C140 the script recommended [[1, 225], [3, 839], [11, 106], [43, 481]]
Normally we would do between a t35-t45 on this number or 1/4 to 1/3 of the digits. We wouldn't consider running any curves at 43e6. This suggests mostly skipping 11e6 and running a decent amount of 43e6.
It would be nice to use fivemack's script when planning ecm for yoyo@home in the future once it is fully finished.
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P73 found by a yoyo@home user yoyo GMP-ECM 3 2017-11-08 15:20
yoyo@home and wikipedia Dubslow Factoring 1 2015-12-06 15:56
Yoyo factors 10metreh ElevenSmooth 20 2013-05-14 03:27
Anyone want to compile an OS X ecm for yoyo? jasong GMP-ECM 1 2009-03-14 11:22
Second yoyo-BOINC factor wblipp ElevenSmooth 0 2009-02-20 00:25

All times are UTC. The time now is 09:07.

Tue May 18 09:07:14 UTC 2021 up 40 days, 3:48, 0 users, load averages: 1.22, 1.67, 1.77

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