mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2016-12-16, 21:55   #1
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

69016 Posts
Default 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?
3.14159 is offline   Reply With Quote
Old 2016-12-16, 22:04   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

446510 Posts
Default

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.
VBCurtis is online now   Reply With Quote
Old 2016-12-16, 22:35   #3
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default

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
3.14159 is offline   Reply With Quote
Old 2016-12-16, 23:58   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

5×19×47 Posts
Default

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
VBCurtis is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A next big thing jasonp Operation Kibibit 23 2012-08-28 12:46
my thing firejuggler Aliquot Sequences 1 2010-05-31 06:57
Very strange thing nngs Software 4 2007-04-14 22:08
Hm... strange thing... Yxine Factoring 1 2006-08-10 13:48
Can not be a good thing :( SB2 3*2^n-1 Search 7 2004-09-23 08:48

All times are UTC. The time now is 19:33.

Mon Nov 23 19:33:40 UTC 2020 up 74 days, 16:44, 2 users, load averages: 2.67, 2.70, 2.64

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