mersenneforum.org ecm thing
 Register FAQ Search Today's Posts Mark Forums Read

 2016-12-16, 21:55 #1 3.14159     May 2010 Prime hunting commission. 24×3×5×7 Posts ecm thing I haven't been here for a while, and I couldn't find much of anything on this by searching it up, so here goes: is there a nice way to calc the odds of finding an n-digit factor after running a curve at a certain b1?
 2016-12-16, 22:04 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 10000110110102 Posts Do you mean specifically n digits, like "what are my chances of finding specifically a 48 digit factor if I run this curve?", or do you mean less than or equal to n digits? Note your odds depend more on the amount of previous ECM done than they do on the specific bounds of the curve you plan to run, unless your planned bound is vastly larger than previous ECM efforts. For instance, running a single curve at B1 = 3e6 has a nice chance to find a 25 digit factor, if no ECM has previously been run; but if a t35 has already been completed that same curve's chance to find a 25 digit factor is nil.
2016-12-16, 22:35   #3
3.14159

May 2010
Prime hunting commission.

32208 Posts

Quote:
 Do you mean specifically n digits, like "what are my chances of finding specifically a 48 digit factor if I run this curve?"
something like that, yes.

to clarify, it would be very nice if there were a way to get the odds of an n-digit factor being found after an amount of curves at a certain b1 (e.g. odds of finding a p35 factor after 100 curves at b1=5e6)

Last fiddled with by 3.14159 on 2016-12-16 at 22:36

 2016-12-16, 23:58 #4 VBCurtis     "Curtis" Feb 2005 Riverside, CA 2·3·719 Posts You should start with "odds this composite *has* a 35-digit factor." Absent any knowledge of the number's special form, that's about 1/n, so 1/35 in this case. Then, given there is such a factor to find, and *no* previous ECM attempts, you could calculate your odds of finding the factor after a certain number of curves. That's roughly (1-1/e^(z/y)), where z is the number of curves you plan to run and y is the expected number of curves required to discover a factor of that specific size. y-values are freely available for each n divisible by 5; if you wish to run non-standard B1 bounds, invoking gmp-ecm with "-v" flag will print the expected curve counts. I am not 100% certain about the above formula; I have used it in the past when z is of the same order of magnitude of y (say, 2000 curves when 4400 is the expected number of curves), but I believe it's an approximation when z is a few hundred or more that isn't quite accurate if you're running a very small number of curves. EDIT: Note that previous ECM failures alter the first probability- it is less likely a factor of the desired size exists when ECM has already been run. Calculating this probability is left as an exercise for the reader. Last fiddled with by VBCurtis on 2016-12-17 at 00:00

 Similar Threads Thread Thread Starter Forum Replies Last Post jasonp Operation Kibibit 23 2012-08-28 12:46 firejuggler Aliquot Sequences 1 2010-05-31 06:57 nngs Software 4 2007-04-14 22:08 Yxine Factoring 1 2006-08-10 13:48 SB2 3*2^n-1 Search 7 2004-09-23 08:48

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

Wed Sep 23 00:46:08 UTC 2020 up 12 days, 21:57, 0 users, load averages: 1.97, 1.77, 1.78