mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   ecm thing (https://www.mersenneforum.org/showthread.php?t=21845)

3.14159 2016-12-16 21:55

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?

VBCurtis 2016-12-16 22:04

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.

3.14159 2016-12-16 22:35

[QUOTE]Do you mean specifically n digits, like "what are my chances of finding specifically a 48 digit factor if I run this curve?"[/QUOTE]

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 p[sub]35[/sub] factor after 100 curves at b1=5e6)

VBCurtis 2016-12-16 23:58

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.


All times are UTC. The time now is 17:48.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.