mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2018-01-13, 17:41   #1
WraithX
 
WraithX's Avatar
 
Mar 2006

23×59 Posts
Default 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
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 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.
WraithX is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 02:02.

Tue Nov 24 02:02:51 UTC 2020 up 74 days, 23:13, 4 users, load averages: 4.45, 4.11, 3.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.