mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2012-09-07, 09:08   #23
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×3×733 Posts
Default

I got curious, and ran a Henry-style test of B1 and B2-scale combinations for a 136-digit number. I tested B1 in 100k increments from 600k to 3M, and B2scales of 1, 1.5, and 2. B2scale 2 results in stage 2 times less than but close to stage 1 times for this number, so I chose not to run B2scale 3 or 4.

Conclusions:
It. Does. Not. Matter.
For example, on default B2, B1 = 700k expects 4.86h for a T35, while B1 = 3M expects 4.85h. Times varied from 4.62h to 5.12h in between those extremes. I retested some outliers to see if a particular B1 was really faster (or slower); those with two averaged runs are in italics. Variances between double-runs was over a tenth of an hour each time, indicating most of the differences on this chart are noise.

Since 2/3rds of the suggested B1 and triple the suggested B1 are both faster than the suggested B1 = 1M for this level, I conclude one might choose to use the next-higher-level B1 for testing; any time lost at the current level is made up for by the vastly increased chance to find a larger factor. So, instead of 910 curves at 1M for a T35, 324 curves at 3M would take roughly the same time but find more factors larger than 35 digits.

One possibly interesting conclusion: In each column, the fastest time occured at the largest B1 that used B2 = 2.1e9.
So, Walter, I think we see why iterating B1 also doesn't matter.
-Curtis
Attached Files
File Type: zip T35testing.zip (3.3 KB, 51 views)

Last fiddled with by VBCurtis on 2012-09-07 at 09:11
VBCurtis is offline   Reply With Quote
Old 2012-09-07, 20:57   #24
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

573210 Posts
Default

As B2 gets modified the k(number of sections it divides the B2 range into) changes. The more times it splits it up the less efficient it gets. If k is higher then it uses less memory. k=1 seems to slow it down on my pc which I would guess is because of some memory bottleneck. Maybe this will force k up higher for much larger B2s.
The default B2 for 1e6 is k=6. This is too high. I found after playing around for a while that k=3 seems optimal on my pc for varying B1s with k=2 shortly behind. It isn't a very exact science as we have to contend with what B2s are available for each value of k(given 1 B2 all other B2s with that k are approx B2*4^x). Providing concrete data to back this up could be quite difficult. We are basically running into the design of gmp-ecm.

2.1e9 is a B2 value with k=3 which is why it is better than 2.85e9 above it which is k=4. Below it we have 1.43e9 which is k=2 which is in general closer.
henryzz is offline   Reply With Quote
Old 2012-09-07, 21:15   #25
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

56308 Posts
Default

I made a c179 = p30*p150 and ran curves on the c179. At B1=250k it took 8,852 curves to find the p30 25 times, while at B1=240k it took 8,218 curves to find the p30 25 times.

Is this a viable (but very slow) way to test this? I know you would probably have to run a lot more curves finding the factor 100 or more times and look at the mean number of curves per factor and the variance.

Last fiddled with by ATH on 2012-09-07 at 21:24
ATH is online now   Reply With Quote
Old 2012-09-08, 17:29   #26
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·3·733 Posts
Default

Quote:
Originally Posted by ATH View Post
I made a c179 = p30*p150 and ran curves on the c179. At B1=250k it took 8,852 curves to find the p30 25 times, while at B1=240k it took 8,218 curves to find the p30 25 times.

Is this a viable (but very slow) way to test this? I know you would probably have to run a lot more curves finding the factor 100 or more times and look at the mean number of curves per factor and the variance.
Because the ECM process is has known probabilities, running an actual trial is less accurate than merely computing the expected times. However, running 25 (or 100) curves at each setting and averaging the expected times is a much better plan than just one.

Your method finds the mean of a random sample- useful when the underlying statistic is not understood. To see this, calculate how many curves are expected to find that factor 25 times, and then look at how your actual result varies from the expectation. The expectation is "correct", while your 8852 will vary quite a bit if you repeat the test.
-Curtis
VBCurtis is offline   Reply With Quote
Old 2012-09-12, 00:57   #27
Walter Nissen
 
Walter Nissen's Avatar
 
Nov 2006
Terra

2×3×13 Posts
Question

Quote:
Originally Posted by VBCurtis View Post
instead of 910 curves at 1M for a T35, 324 curves at 3M would take roughly the same time but find more factors larger than 35 digits.
Yes.
Quote:
I think we see why iterating B1 also doesn't matter.
I don't see this .
If some curves are run at a somewhat smaller B1 , a factor may be
found quickly .
If B1 escalates , the probability of finding larger factors is
increased .
Incrementation would seem to be sharing in the best of both
worlds .
Incrementation has the feel of being optimal , and is consistent
with the theory that you learn something from every curve run , and
also with reports that factors are found most often in the early
curves at a given level .

I'm often a strong advocate of the benefits of standardization ,
but I've never detected any benefit of using only standard B1's .


> One possibly interesting conclusion: In each column, the fastest
> time occured at the largest B1 that used B2 = 2.1e9.

Yes , I'm wary of artifacts introduced by specific details of the
technologies used .
So , my hunger for data such as henryzz , etc. , are providing is
strong , but I don't expect results necessarily to be repeatable
across different systems or even at different times of day or on
different days of the week .
Walter Nissen is offline   Reply With Quote
Old 2012-09-14, 03:06   #28
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×3×733 Posts
Default

Walter-
Decide on a rough iteration schedule you think will be more efficient at finding factors, and compute the expected time to achieve a T30, T35, and T40 for your method. I think that your argument has merit, but without actual data it's mere speculation about what might be more efficient.

If you do this, I will use my data to find the B1s I believe are most efficient, and we'll compare. I agree with you about the difficulty in repeating time measurements, but I think you'd want to be more than 10% faster iterating to make it worth the hassle of having unclear measurements of the amount of work done.

-Curtis

Edit: To address your "I don't see this": If the expected time to run a T35 is within 5% for 7e5 through 3e6, I would prefer to not iterate through all those B1s- I would jump straight to 3e6 to do all my T35 testing, with the bonus that I get quite a bit more work done on T40 than your iterations would. This is why I want you to figure out an iteration schedule- perhaps you move B1 up so aggressively that you can counteract this effect.

Last fiddled with by VBCurtis on 2012-09-14 at 03:11
VBCurtis is offline   Reply With Quote
Old 2012-09-14, 16:09   #29
chris2be8
 
chris2be8's Avatar
 
Sep 2009

111011110112 Posts
Default

What about GPU-ECM? All curves on each run on the GPU must have the same B1, and B2 is probably best set to the value you can get the curves from 1 run to while the GPU does another set. Which varies with the relative speed of your GPU(s) and your CPU(s).

The good news is that you can do a lot more curves per day by adding a GPU to your farm than using CPUs only.

Chris
chris2be8 is offline   Reply With Quote
Old 2012-09-14, 16:24   #30
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25×149 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
What about GPU-ECM? All curves on each run on the GPU must have the same B1, and B2 is probably best set to the value you can get the curves from 1 run to while the GPU does another set. Which varies with the relative speed of your GPU(s) and your CPU(s).

The good news is that you can do a lot more curves per day by adding a GPU to your farm than using CPUs only.

Chris
AFAIR, GPU-ECM was limited to 1000 (bits|digits), and to Stage1 only. Is there a site that reports advances in the development?

Luigi
ET_ is offline   Reply With Quote
Old 2012-09-15, 16:48   #31
chris2be8
 
chris2be8's Avatar
 
Sep 2009

77B16 Posts
Default

All I know about it is what it says in http://mersenneforum.org/showthread.php?t=16480

It's always been stage 1 only. The idea is that doing stage 1 on the GPU means the CPU only has to do stage 2. Which speeds things up a lot.

Chris
chris2be8 is offline   Reply With Quote
Old 2014-02-14, 23:39   #32
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×3×733 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
Walter-
Decide on a rough iteration schedule you think will be more efficient at finding factors, and compute the expected time to achieve a T30, T35, and T40 for your method. I think that your argument has merit, but without actual data it's mere speculation about what might be more efficient.

If you do this, I will use my data to find the B1s I believe are most efficient, and we'll compare. I agree with you about the difficulty in repeating time measurements, but I think you'd want to be more than 10% faster iterating to make it worth the hassle of having unclear measurements of the amount of work done.

-Curtis

Edit: To address your "I don't see this": If the expected time to run a T35 is within 5% for 7e5 through 3e6, I would prefer to not iterate through all those B1s- I would jump straight to 3e6 to do all my T35 testing, with the bonus that I get quite a bit more work done on T40 than your iterations would. This is why I want you to figure out an iteration schedule- perhaps you move B1 up so aggressively that you can counteract this effect.
I have played around with this quite a bit over the last few months, and am now convinced that iterating B1 up slowly is a less efficient way to find factors than 'jumps' in B1. The reason is Henry's observation above- ECM is more efficient when k=2 or k=3 than it is for any higher k, so long as you have sufficient memory.

One can mitigate this by forcing k=2 or k=3, but then one is using B2 values for some B1s less efficient overall than sticking to a single best B1/B2 combo for a given size of desired factor.

Optimized B1 values for each T-level are significantly higher than standard values, and 5-8% faster than standard values. I suspect my claims earlier in this thread about B2scale values of 4 or higher were merely fortunate to land on k=2 or k=3 B2-values.

If you wish to experiment, GCM 6.4.4 has the following B1 ranges you may wish to try:
k=2: 8-9M, 21-26M, 58-68M, 150-180M, 420-? M
K=3: 10-12M, 28-34M, 70-80M, 190-240M

Note that forcing with the -k option actually changes the B2 selected, rather than the manner in which ECM uses memory for a given B2. So, -k will have effects somewhat similar to -B2scale.
VBCurtis is offline   Reply With Quote
Old 2014-02-15, 00:23   #33
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
I have played around with this quite a bit over the last few months, and am now convinced that iterating B1 up slowly is a less efficient way to find factors than 'jumps' in B1.
Since "iterating B1 up slowly" and "jumps in B1" are both meaningless
without definition, it is impossible to either confirm or refute your
assertion. The decision here is NOT the choice of B1 and B2.
Rather, it is the SIZE OF THE FACTOR you are looking for. Once you
determine that, the optimal choice of B1 and B2 for that particular size
can be extracted from existing tables (or by running GMP-ECM)

Quote:


The reason is Henry's observation above- ECM is more efficient when k=2 or k=3 than it is for any higher k, so long as you have sufficient memory.
What is 'k'? It too is undefined.

<snip>


Quote:
If you wish to experiment,
Experiments are not needed. My paper with Sam Wagstaff, "A Practical
Analysis of ECM' shows how to change B1 optimally following a failure.
It does so in a mathematically exact way: The a priori distribution of
(size of) factors of a large integer is known. One can use, e.g. Dickman's
function, or the fact that a large integer N has a factor between
x and x^(1+e) with probability e/(e+1). This becomes a prior (In
Bayesian terminology). The failure of ECM at a particular choice of
B1 & B2 gives a sample density function . One then uses Bayes' Theorem
to compute a posterior. The mean of the posterior minimizes the
unit linear loss function. Since computer cost is linear in time, this
method is optimal.

One starts by looking for a factor near some choice X, running some
ECM trials with B1 and B2 chosen optimally for that value of X, then
applies the above procedure. The optimal B1, B2 choices for X are
implementation and machine dependent, but the procedure for
optimally changing B1, B2, does not so depend.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ECM - why 3 curves? James Heinrich PrimeNet 3 2017-11-14 13:59
JKL-ECM: ECM using Hessian curves CRGreathouse Software 1 2017-09-06 15:39
Need help with elliptic curves... WraithX Math 12 2010-09-29 09:34
Curves needed henryzz GMP-ECM 3 2007-12-21 16:13
Elliptic curves in NFS otkachalka Factoring 5 2005-11-20 12:22

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

Wed Oct 28 05:13:27 UTC 2020 up 48 days, 2:24, 2 users, load averages: 1.77, 1.56, 1.43

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.