mersenneforum.org ECM's Repeating?
 Register FAQ Search Today's Posts Mark Forums Read

 2017-08-26, 23:42 #1 storm5510 Random Account     Aug 2009 36348 Posts ECM's Repeating? In the image attached, there appears to be repeating of ECM factoring. All have the same bounds and the same number of curves. The TF depths increase, however there is no parameter in a worktodo entry that indicates how far an exponent has been factored. Sample: Code: ECM2=1,2,,-1,50000,5000000,3 So, someone educate me. What am I missing here? Attached Thumbnails
2017-08-27, 00:12   #2
GP2

Sep 2003

1010000110002 Posts

Quote:
 Originally Posted by storm5510 In the image attached, there appears to be repeating of ECM factoring. All have the same bounds and the same number of curves. The TF depths increase, however there is no parameter in a worktodo entry that indicates how far an exponent has been factored. So, someone educate me. What am I missing here?
ECM is like throwing darts at a dartboard. You never know which one might hit the bullseye. It makes perfect sense to just keep throwing darts.

Although there does eventually come a point where you've carpet-bombed the dartboard and it turns out it (almost certainly) doesn't have a bullseye, so then you might start throwing at a more distant dartboard and hope that one does have a bullseye. The more distant the dartboard, though, the more darts you have to throw to make sure you have saturation coverage, and the more effort it takes to throw them. So maybe you give up instead.

TF, on the other hand, is deterministic. If you search to a given bit-depth, then you either find a factor or you don't, and there's no sense duplicating the same search twice. Same with P−1 by the way: it makes no sense to repeat a P−1 test with the same B1 and B2 parameters.

Last fiddled with by GP2 on 2017-08-27 at 00:32 Reason: added "almost certainly"

2017-08-27, 00:30   #3
storm5510
Random Account

Aug 2009

22×487 Posts

Quote:
 Originally Posted by GP2 ECM is like throwing darts at a dartboard. You never know which one might hit the bullseye. It makes perfect sense to just keep throwing darts. Although there does eventually come a point where you've carpet-bombed the dartboard and it turns out it doesn't have a bullseye, so then you might start throwing at a more distant dartboard and hope that one does have a bullseye. The more distant the dartboard, though, the more darts you have to throw to make sure you have saturation coverage, and the more effort it takes to throw them. So maybe you give up instead...
I get it. Thank you for the reply.

2017-08-27, 14:45   #4
LaurV
Romulan Interpreter

Jun 2011
Thailand

22×2,381 Posts

Quote:
 Originally Posted by storm5510 All have the same bounds and the same number of curves.
Additionally to what GP2 (in a very nice metaphor) said, yes, ECM starts with a "random seed" which makes the probability of two people doubling the same work very low, and you can look to this report, to have an idea about the limits and the number of curves needed at each level.

For example (see the tables), if you do about 4700 curves with B1=3M, this leaves an extremely low probability (close to zero) that a factor of 40 digits remained undiscovered. Sometimes they do indeed remain hidden (depending on their ECM "smoothness") and they are found much later, at higher bounds, or at NFS, etc (like when we factor aliquot sequences) and then we talk about an "ECM miss". But that is another story...

Last fiddled with by LaurV on 2017-08-27 at 14:51

2017-08-27, 16:24   #5
storm5510
Random Account

Aug 2009

22·487 Posts

Quote:
 Originally Posted by LaurV Additionally to what GP2 (in a very nice metaphor) said, yes, ECM starts with a "random seed" which makes the probability of two people doubling the same work very low...
A random seed value. I see now why so many tests "appear" repeated, when they are actually not. A single exponent could possibly accumulate thousands of curves, or more, depending on the size.

Thank you for the report link. I will study it in more detail.

2017-08-27, 18:44   #6
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

10,723 Posts

Quote:
 Originally Posted by LaurV For example (see the tables), if you do about 4700 curves with B1=3M, this leaves an extremely low probability (close to zero) that a factor of 40 digits remained undiscovered.
I'm too lazy to compute a precise figure for the probability you describe but a quick mental calculation suggests that it's around 10%. Whether thas is "extremely low" and "close to zero" is a value judgement.

2017-08-27, 22:33   #7
ATH
Einyen

Dec 2003
Denmark

32·349 Posts

Quote:
 Originally Posted by LaurV For example (see the tables), if you do about 4700 curves with B1=3M, this leaves an extremely low probability (close to zero) that a factor of 40 digits remained undiscovered. Sometimes they do indeed remain hidden (depending on their ECM "smoothness") and they are found much later, at higher bounds, or at NFS, etc (like when we factor aliquot sequences) and then we talk about an "ECM miss". But that is another story...
I think ECM bounds are calculated at each digit level, so that the risk of missing a factor at that size after doing the prescribed number of curves is: 1/e ~ 37%. So there is still a fair chance of a missed factor, but then they can be found at higher bounds as well.

This way of doing ECM is supposedly the optimal way of searching for factors from that paper on ECM bounds that RDS co-authored and always referred to.

Last fiddled with by ATH on 2017-08-27 at 22:35

2017-08-27, 22:58   #8
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by ATH I think ECM bounds are calculated at each digit level, so that the risk of missing a factor at that size after doing the prescribed number of curves is: 1/e ~ 37%. So there is still a fair chance of a missed factor, but then they can be found at higher bounds as well.
Right. But I would have thought that finishing the next level above a given level would take the chance down from 37% to much less than 10%. In any case, the chance of missing a factor of the last level you finish, if you don't do any more at higher levels, is about 37%.

 2017-08-31, 14:45 #9 LaurV Romulan Interpreter     Jun 2011 Thailand 22·2,381 Posts That is right, I stand corrected. What I was thinking is that as you go higher and higher, your "chances" to miss factors of a specified size gets asymptotically lower and lower... Anyhow, the man got the idea...
 2017-11-11, 01:08 #10 storm5510 Random Account     Aug 2009 22·487 Posts I have noticed after running ECM's for a while that the bounds in the worktodo file always seem to be the same: B1=50000, B2=5000000. This holds regardless of the size of the exponent. Is this a constant, or does Prime95 change this as it runs? There is also a relationship between the RAM allocation and the size of the exponents assigned. This, I understand. However, if I go beyond 2560M, I start seeing pauses in Stage 2 with some as long as 20 seconds. The CPU load does not decrease during this time. Perhaps I am limited because of the total RAM in this machine, 8GB. I have been meaning to increase it to 16GB, but never seem to get around to getting it done.
 2017-11-11, 10:08 #11 thyw   Feb 2016 ! North_America 10100002 Posts Are you assigning it with https://www.mersenne.org/manual_assignment/ ? It should give you the corrent B1 B2 in the assigment (just tried out with a 10k number), and you can manually edit the number of curves in the worktodo. Possibly (maybe) the bounds too. https://www.mersenne.org/report_ecm/ second table as other commenters pointed out. It's giving you the column which isn't done. Last fiddled with by thyw on 2017-11-11 at 10:09