

Thread Tools 
20180510, 00:22  #1  
Mar 2006
2^{3}×59 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
7221_{10} 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
1 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). 
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 