mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2017-08-26, 23:42   #1
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009

1,987 Posts
Default 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,<exp>,-1,50000,5000000,3
So, someone educate me. What am I missing here?
Attached Thumbnails
Click image for larger version

Name:	ecm.JPG
Views:	200
Size:	79.4 KB
ID:	16735  
storm5510 is offline   Reply With Quote
Old 2017-08-27, 00:12   #2
GP2
 
GP2's Avatar
 
Sep 2003

258510 Posts
Default

Quote:
Originally Posted by storm5510 View Post
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"
GP2 is offline   Reply With Quote
Old 2017-08-27, 00:30   #3
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009

1,987 Posts
Default

Quote:
Originally Posted by GP2 View Post
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.
storm5510 is offline   Reply With Quote
Old 2017-08-27, 14:45   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

264E16 Posts
Default

Quote:
Originally Posted by storm5510 View Post
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
LaurV is offline   Reply With Quote
Old 2017-08-27, 16:24   #5
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009

37038 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
storm5510 is offline   Reply With Quote
Old 2017-08-27, 18:44   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

103·107 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
xilman is offline   Reply With Quote
Old 2017-08-27, 22:33   #7
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3,191 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
ATH is offline   Reply With Quote
Old 2017-08-27, 22:58   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by ATH View Post
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%.
CRGreathouse is offline   Reply With Quote
Old 2017-08-31, 14:45   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

231168 Posts
Default

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...
LaurV is offline   Reply With Quote
Old 2017-11-11, 01:08   #10
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009

1,987 Posts
Default

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.
storm5510 is offline   Reply With Quote
Old 2017-11-11, 10:08   #11
thyw
 
Feb 2016
! North_America

23×11 Posts
Default

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
thyw is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Repeating Digits of Pi a1call Math 10 2017-10-05 15:58

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


Sat Nov 27 00:16:36 UTC 2021 up 126 days, 18:45, 1 user, load averages: 1.40, 1.32, 1.30

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.