2018-01-13, 17:41 | #1 |
Mar 2006
13·41 Posts |
ECM success/failure probability graphs, the interactive online version!
I have created a web page that graphs out the probabilities of success/failure for ecm to find factors of various sizes for a specified amount of work.
tl;dr - Page here: www.wraithx.net/math/ecmprobs/ecmprobs.html 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 GMP-ECM 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 recommend 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 (differential-probability-at-d * 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 100-400 digits, and B1 in [100e3, 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, or 1.1e7, or 260e6, or 29e8, etc. You can view the page here: www.wraithx.net/math/ecmprobs/ecmprobs.html I'd be interested to hear what people think of this page, and, more importantly, if the math on the page is correct. The data for the runtimes is "pretty large" (about 2.6MB currently), so it may take a moment to load when you first visit the page. The javascript for the plot/graph library (plotly.js) is also pretty large at around 2.2MB. |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Progress graphs | fivemack | NFS@Home | 3 | 2016-05-06 22:09 |
NFS success probability in practice | paul0 | Factoring | 2 | 2015-02-23 03:55 |
Known factors distribution graphs | James Heinrich | Data | 21 | 2013-09-26 19:54 |
Individual overall statistics graphs | Chuck | GPU to 72 | 4 | 2012-08-20 23:58 |
JavaScript for 2-player interactive game-playing? | ewmayer | Programming | 2 | 2006-02-04 19:22 |