ECM success/failure probability graphs, and runtime information, the interactive online version!

[WraithX]

tl;dr - Two pages available:

First page has probability graphs from given work on top, and EFS graphs based on future work on bottom:
www.wraithx.net/math/ecmprobs/ecmprobs.html

Second page will plot out runtime and memory requirements for work on a d-digit number (d in [100-500]).
www.wraithx.net/math/ecmprobs/ecmtimes.html

Camera icon in each graph allows you to save a snapshot of that graph as a png.

The first page I have created graphs out the probabilities of success/failure for ecm to find factors of various sizes for a specified amount of work.

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:

   B1 ,     B2  ,    10   ,    11   ,    12
  1000,    51606, 3.912815, 6.683098, 12.19323
100000, 40868532, 1.157822, 1.321335,  1.521006

Which lists B1/B2 values used by GMP-ECM v7, and how many curves are recommended to find a factor of a particular size.
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 (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-500 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 d-digit 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 gmp-ecm.

I'd be interested to hear what people think of these pages, and, more importantly, if the math is correct.

[Dubslow]

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 n-size factor" to "these odds to find a factor of size-x over a broad range of sizes", which is ultimately more important.

[hardmath]

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...t-prime-factor), "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).

[Tyler Busby]

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 GMP-ECM binaries I've seen floating around) I mostly use ECM with YAFU, so I'm not intimately familiar with how I would benchmark GMP-ECM 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 12-16 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 GMP-ECM one liner that can be used to measure each value at the specific B1 value for a similarly sized composite.