mersenneforum.org ECM success/failure probability graphs, and runtime information, the interactive online version!
 Register FAQ Search Today's Posts Mark Forums Read

2018-05-10, 00:22   #1
WraithX

Mar 2006

11×43 Posts
ECM success/failure probability graphs, and runtime information, the interactive online version!

Quote:
 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:

Code:
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.
Attached Files
 ecmtimes_100d-500d_10e3-990e6.zip (1.13 MB, 225 views) ecmprobs_1e3-50e9.zip (1.87 MB, 201 views)

 2018-05-16, 01:27 #2 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2019-09-15, 17:14 #3 hardmath   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...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).

 Similar Threads Thread Thread Starter Forum Replies Last Post WraithX Math 0 2018-01-13 17:41 bgbeuning GPU Computing 2 2017-01-31 20:19 froderik GPU Computing 4 2016-10-30 15:29 paul0 Factoring 2 2015-02-23 03:55 ewmayer Programming 2 2006-02-04 19:22

All times are UTC. The time now is 09:52.

Mon May 17 09:52:08 UTC 2021 up 39 days, 4:33, 0 users, load averages: 1.18, 1.25, 1.41