mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-12-10, 01:33   #1
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2·3·19·67 Posts
Default akruppa - B2 help please

I'm tracking ECM effort in the v5 server. I compute total_ecm_effort as sum (curve_count * B1). When this total gets to certain levels I issue ECM assignments with a larger B1 value.

The problem? The summed B1 values assume a B2 value of 100*B1. When I use GMP-ECM B2 is often much higher than 100*B1. I need a simple formula that given B1 and B2 it returns a multiplier. I apply this multiplier to the curve count to get a rough equivalent of the number of B2=B1*100 curves. Accuracy is not critical - a 10-20% error would be fine.

For example, on a number I'm currently atttacking B2 = 7000 * B1. According to GMP-ECM one of these curves equals 2.3 curves of B2 = 100 * B1.

My placeholder routine on the server is this:

function normalized_B1 ($B1, $B2)
{
$ratio = (1.0 * $B2) / $B1;
if ($ratio < 7) return ($B1 * 0.4);
if ($ratio < 30) return ($B1 * 0.6);
if ($ratio < 70) return ($B1 * 0.8);
if ($ratio < 300) return ($B1);
if ($ratio < 700) return ($B1 * 1.4);
if ($ratio < 3000) return ($B1 * 1.7);
if ($ratio < 7000) return ($B1 * 2.3);
return ($B1 * 2.8);
}
Prime95 is offline   Reply With Quote
Old 2007-12-11, 13:12   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

I get these figures for the expected number of curves, all without Brent-Suyama extension:

B1=1e6
B2: Curves to find p35: Ratio:
1e6 14317 0.12
1e7 3388 0.49
1e8 1674 1
1e9 993 1.68
1e10 639 2.62
1e11 430 3.89
1e12 297 5.62

B1=1e7
B2: Curves to find p45: Ratio:
1e7 94363 0.12
1e8 22594 0.5
1e9 11286 1
1e10 6779 1.66
1e11 4421 2.55
1e12 3015 3.74
1e13 2113 5.34

B1=1e8
B2: Curves to find p55: Ratio:
1e8 410456 0.12
1e9 101581 0.51
1e10 51549 1
1e11 31434 1.64
1e12 20823 2.47
1e13 14436 3.57
1e14 10291 5.00

The closest function I got to these ratios is
0.12 + 0.88 * (log_10(B2 / B1) / 2) ^ 1.5, which produces for log_10(B2 / B1) = 0 ... 6
0: 0.1200000000000000000000000000
1: 0.4311269837220809107363715193
2: 1.000000000000000000000000000
3: 1.736663230236897544810207489
4: 2.609015869776647285890972155
5: 3.598505426185217265198782899
6: 4.692614131981836054912458342


The values for 1 and 6 are somewhat too low, but such B2/B1 ratios will probably not be used much. For 3 it's somewhat too high. If you want really accurate estimates, you could call Pari/GP as an external program and let the rho.gp script compute probabilities. Or I'll write a small wrapper around the C code in GMP-ECM.

Alex

Last fiddled with by akruppa on 2007-12-11 at 21:39 Reason: Should be 0.12 + 0.88 * ... I guess
akruppa is offline   Reply With Quote
Old 2007-12-11, 15:03   #3
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2·3·19·67 Posts
Default

Thanks, Alex. Your formula was exactly what I needed. Like I said too much accuracy in curve counting is not critical as the only consequence is you move on to a larger B1 a liitle too early or a little too late - no big deal.

Another ECM puzzle for you: I want to hand out ECM assignments such that I roughly maximize the chance of finding a factor for a given effort. What formula would you use given the quantities total_ecm_effort (the sum of completed B1 values) and N (the Mersenne exponent). Ignore the step function nature of FFT lengths and assume the time it takes to run an ECM curve is proportional to N (log N).

A simpler way to phrase this is: If an exponent has had a total_ecm_effort X, what is the probability the next ECM curve will find a factor (to make life easier, ignore the step nature of assigned B1 values).

Given such a formula I can then use the expected CPU run time to maximize factors found.
Prime95 is offline   Reply With Quote
Old 2007-12-12, 17:58   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

This isn't an easy question. You'd want to compute the distribution of remaining factors given an a priori distribution (i.e. 1/n probability of n-bit factor), adjust by taking previous factoring effort into account and choose the ECM parameters so that the scalar product of that distribution and ECM's probability of finding factors of n bits, divided by the time ECM with those parameters would use is maximal. This is a bit messy.

This is what Silverman and Wagstaff described in the "Practical Analysis" paper (which I have to admit still haven't read as carefully as I should! ). As I understood it, the scheme of doing the expected number of curves for a certain factor size, then moving on to a size 5 digits larger is a good approximation to exactly this goal: maximising each curve's probability of finding a factor per unit time. If you want more precise parameter choice, all I can offer is code to compute ECM's proability of success for given parameters/factor sizes, so you can model the Bayesian process.

Alex
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I'd like to know why akruppa threatened to ban me for 2 months SaneMur Forum Feedback 4 2012-02-01 16:29

All times are UTC. The time now is 21:13.


Sun Oct 24 21:13:37 UTC 2021 up 93 days, 15:42, 1 user, load averages: 0.83, 0.95, 1.01

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.