

Thread Tools 
20180510, 00:22  #1  
Mar 2006
13×41 Posts 
ECM success/failure probability graphs, and runtime information, the interactive online version!
Quote:
Along with this graph I also calculate the "expected factor size", or EFS for short, of the displayed curves. I believe the calculated EFS describes the most likely size of a factor to be found with the given amount of work. Below this graph is another graph where you can enter various parameters to find out how the EFS changes when running additional curves over time x. Here's my description of how the success/failure curves are calculated. First, I generated a table of values from GMPECM v7 that look similar to: Code:
B1 , B2 , 10 , 11 , 12 1000, 51606, 3.912815, 6.683098, 12.19323 100000, 40868532, 1.157822, 1.321335, 1.521006 I gathered these data with B1 values between 1e3 and 50e9, and for factor sizes from 10 to 100 digits. I then use the inverse of the recommended curves as the probability, p, for ecm to find a factor of that size. I then calculate the chance to fail to find a factor of that size after running n curves as = (1  p)^n. I then, if specified, combine curves run at different B1 values by multiplying their failure probabilites together. I calculate the success probability as = 1  f, where f is the final failure probability for a particular factor size. I then numerically differentiate the failure probabilities and generate the differential probability curve. I then calculate "Expected factor size" = sum over all factor sizes d in [10,100] of (differentialprobabilityatd * d) I got the idea for the differential probability from RDS's paper "A Practical Analysis Of The Elliptic Curve Factoring Algorithm". He describes calculating the expected value of the posterior from the differential probability on page 456. I am still collecting runtime data for ecm curves at various B1 values, but I have an early version ready for testing. It contains ecm v7 (param=1) probabilities for B1 in [1e3, 50e9]*1, inclusive. It has runtime data available for numbers between 100500 digits, and B1 in [10e3, 990e6]*1, inclusive. *1 B1 values available are of the form ab * 10^c, with a in [1,9], b in [0,9], and c in [3,9]. ie, 10e3, 38e3, 6e4, 7.5e5, 1e6, 11e6, 43e6, 110e6, 26e7, 9.9e8, etc You can view the probabilities page here: www.wraithx.net/math/ecmprobs/ecmprobs.html I have updated the page so that it only loads a small part of the runtime data. You have to click the "Load Runtime Data" button once before you can plot runtime information. Then, once the data for that digit size has been loaded, you can "Update Runtime Graph" several times with various new B1 values to see how they compare to each other. The javascript for the plot/graph library (plotly.js) is pretty large at around 2.2MB, so the first visit to the page may take a couple of seconds to load. The second page I created generates a graph that shows how much time and memory is needed to run a curve at various B1 values for a user specified ddigit number. The runtimes I have gathered look pretty linear in B1+B2 time. There will be some "small" bumps in the data since this data was gathered on my daily use computer. You can view the runtime/memory page here: www.wraithx.net/math/ecmprobs/ecmtimes.html Each graph has a camera icon in the top right corner. You can use this to save a png image of the current graph. If anyone wants to do their own work with the data, I am attaching two zip files below. One contains all of the runtime data I've collected so far, and the other contains all of the probability data that I've gathered from gmpecm. I'd be interested to hear what people think of these pages, and, more importantly, if the math is correct. 

20180516, 01:27  #2 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1C35_{16} Posts 
This is great, thanks. Although I can't do much about it right now, I'm pretty sure this will turn out to be our best resource. Perhaps Tom will be able to improve his ecm toy with this data?
It's also remarkably similar to my own thoughts, which were of course prompted by your thoughts on this topic. The differential probability is by far the most interesting to me, since it helps generalize an ECM curve from "these odds to find an nsize factor" to "these odds to find a factor of sizex over a broad range of sizes", which is ultimately more important. 
20190915, 17:14  #3 
Apr 2019
2 Posts 
I appreciate your work in setting up [that calculator](http://www.wraithx.net/math/ecmprobs/ecmprobs.html) online. I linked to it (as well as to this thread) in a recent update to an answer I posted [at Math.SE](https://math.stackexchange.com/quest...tprimefactor), "Expected number of digits of the smallest prime factor".
The estimate I got for that problem turned out to be accurate, but I'm thinking it was an illustration of why it's better to be lucky than good! In any case I was using somewhat different assumptions, and I point it out mainly to motivate my feedback. I would incorporate the digit size of the number to be factored into the upper computation, not only into the bottom one. It is after all quite typical that we know the number to be factored is composite, and therefore that the smallest prime factor is at most the square root of it (half the number of digits in size, more or less). 
20230119, 18:18  #4 
Jan 2023
31_{8} Posts 
Love this tool! I am curious if specific processors (namely mine) would maybe have performance responses to B1 size that were dissimilar to a Xeon 2687W v4, and if you used any specific scripts to benchmark at certain sizes that I could try out! (Would also be useful for benchmarking different GMPECM binaries I've seen floating around) I mostly use ECM with YAFU, so I'm not intimately familiar with how I would benchmark GMPECM on its own. I'm running lots of ECM on F1801 (C377), and just wanted to even more finely tune the point at which I switch B1s from 26e7 to 85e7. Your tool suggests t=59.3, but I wanted to see if that changed with my processor. (Currently I've timed each curve (at 1216 threads) at 43 minutes per curve per thread @26e7, and 131 minutes per curve at 85e7)
Before I begin poking around and trying to inject my own timings into your site, I figured I'd ask you if you had any tooling to make this a little less arduous! And to thank you for making this site! Edit: It just occurred to me to suggest maybe another set of inputs next to the 2 "New B1 Value" inputs, that are timing/ram "overrides" where the user can specify their measured performance, and maybe (though less imperative) a GMPECM one liner that can be used to measure each value at the specific B1 value for a similarly sized composite. Last fiddled with by Tyler Busby on 20230119 at 18:35 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
ECM success/failure probability graphs, the interactive online version!  WraithX  Math  0  20180113 17:41 
mfacktc runtime version 12517  bgbeuning  GPU Computing  2  20170131 20:19 
"CUDA runtime version 0.0" when running mfaktc.exe  froderik  GPU Computing  4  20161030 15:29 
NFS success probability in practice  paul0  Factoring  2  20150223 03:55 
JavaScript for 2player interactive gameplaying?  ewmayer  Programming  2  20060204 19:22 