mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2018-05-10, 00:22   #1
WraithX
 
WraithX's Avatar
 
Mar 2006

11×43 Posts
Default 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
File Type: zip ecmtimes_100d-500d_10e3-990e6.zip (1.13 MB, 225 views)
File Type: zip ecmprobs_1e3-50e9.zip (1.87 MB, 201 views)
WraithX is offline   Reply With Quote
Old 2018-05-16, 01:27   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160658 Posts
Default

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.
Dubslow is offline   Reply With Quote
Old 2019-09-15, 17:14   #3
hardmath
 
Apr 2019

1 Posts
Default

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).
hardmath is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ECM success/failure probability graphs, the interactive online version! WraithX Math 0 2018-01-13 17:41
mfacktc runtime version 12517 bgbeuning GPU Computing 2 2017-01-31 20:19
"CUDA runtime version 0.0" when running mfaktc.exe froderik GPU Computing 4 2016-10-30 15:29
NFS success probability in practice paul0 Factoring 2 2015-02-23 03:55
JavaScript for 2-player interactive game-playing? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.