 mersenneforum.org SNFS(27x) How much ECM before switching to NFS?
 Register FAQ Search Today's Posts Mark Forums Read  2015-06-01, 15:25   #12
wreck

"Bo Chen"
Oct 2005
Wuhan,China

2×5×17 Posts Quote:
 Originally Posted by R.D. Silverman "wreck" is not knowledgeable in this area. He seems to have pulled his ".1" constant from where the sun don't shine. There are two .1 in my statement, the first one is by experience or some small thinking, if you have 1 resource,
then you have 0.1 resource.

the second .1 is come from mersenne.org,
http://www.mersenne.org/various/math.php
which says,
Code:
Looking at past factoring data we see that the chance of finding a factor between 2^X and 2^{X+1} is about 1/x.
From this looking, we can find a factor between 10^x to 10^{x-1} is about 1/x.
So find a factor between 10^55 to 10^60 is about ln(60)-ln(55) = 0.087

I had read your paper that you sent me many years ago, but I could not understant it, it seems like
you only use B2 = k * B1 to judge how many curves and which B1 should select.
But you do not said nfs in that paper,
If ECM use more time than nfs, the direct thinking is switch to nfs.
I do not have profound knowledge about ecm and snfs,
I read some papers about nfs, the ecm is more than a tool to me to use it.

I do not know where the 2/9 come from, but it seems like all persons from this forum use it.   2015-06-01, 16:02   #13
YuL

Feb 2012
Paris, France

7·23 Posts Quote:
 Originally Posted by R.D. Silverman "wreck" is not knowledgeable in this area. He seems to have pulled his ".1" constant from where the sun don't shine. BTW, what is so blankety-blank special about 55 digits??? The real issue is whether you will succeed faster *in expectation* by using NFS or by using ECM. I told you how to do that computation.
If I'm not mistaken your paper states that the probability of having a factor
between y and y^(1+e) is about e/(1+e). If I replace y by 10^55 and e by
1/11, I get probability of having a factor p such that 10^55 < p < 10^60 is
about 1/12 = 0.0833 which is pretty close to 0.1.
Now, why 55 digits? Because a t55 has been run and it produced no factor
(so there is still an 1/e = 0.37 probability of missing a 55 digit factor).
I read your paper but it looks like I won't be able to derive the result
I'm looking for from that reading :).

Last fiddled with by YuL on 2015-06-01 at 16:41 Reason: Typo   2015-06-01, 16:35   #14
R.D. Silverman

Nov 2003

22×5×373 Posts Quote:
 Originally Posted by YuL If I'm not mistaken your paper states that the probability of having a factor between y and y^(1+e) is about e/(1+e). If I replace y by 10^55 and e by 1/11, I get probability of having a factor p such that 10^55 < p < 10^60 is about 1/12 = 0.0833 which is pretty close to 0.1. Now, why 55 digits? Because a t55 has been run and it produced no factor (so there still an 1/e = 0.37 probability of missing a 55 digit factor). I read your paper but it looks like I won't be able to derive the result I'm looking for from that reading :).
So you should now ask yourself about the following problem in conditional probability.

GIVEN that the probability of missing a p55 was 1/e, what is the conditional probability
of finding a factor between 55 and 60 digits? 60 and 65? 65 and 70? etc. This is what Bayes thm
does for us. One can compute the likelihood of suceeding with ECM even though the factor
size is unknown. This tells whether more ECM is worthwhile when you compare the ECM
time against the SNFS time....   2015-06-04, 21:13   #15
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

17·563 Posts Quote:
 Originally Posted by YuL I'm actually thinking about factorization of two numbers one is SNFS 270.7 and the other is SNFS 273.7. The "2/9 of SNFS difficulty" rule suggests doing t60 ...
...but finding a p65 factor would have been harder by ECM than by SNFS, even if it leaves a bit of bitter taste (everyone wants a nice split e.g. p135 * p136, but in factoring it is what it is).
This is not a miss, just normal luck. Having it found by ECM would have been lucky; not having found - normal.

A job well done! Congrats!   2015-06-05, 10:17   #16
YuL

Feb 2012
Paris, France

7×23 Posts Quote:
 Originally Posted by Batalov ...but finding a p65 factor would have been harder by ECM than by SNFS, even if it leaves a bit of bitter taste (everyone wants a nice split e.g. p135 * p136, but in factoring it is what it is). This is not a miss, just normal luck. Having it found by ECM would have been lucky; not having found - normal. A job well done! Congrats!
Thanks. I recognize I was a bit disappointed when I first saw the factors
yesterday, of course p135*p136 would have been wonderful, but a p65 on that
one is certainly not an ECM miss. It's just the way it is, I may be luckier
with the next one who knows.. Two years ago I thought a SNFS(240) was
out of reach and now I just achieved a SNFS(271).

Quote:
 Originally Posted by R.D. Silverman So you should now ask yourself about the following problem in conditional probability. GIVEN that the probability of missing a p55 was 1/e, what is the conditional probability of finding a factor between 55 and 60 digits? 60 and 65? 65 and 70? etc. This is what Bayes thm does for us. One can compute the likelihood of suceeding with ECM even though the factor size is unknown. This tells whether more ECM is worthwhile when you compare the ECM time against the SNFS time....
It is always challenging to exchange with you Mr Silverman
(which is a good thing cause it makes us learn things).
I've been thinking about your above post lately and here is what
I can come up with:

Let N be the number we want to factor, we have
Code:
factor size (digits)    50-55     55-60    60-log10(sqrt(N))
probability             1/11      1/12     1-1/11-1/12 = 109/132
(I suppose probability of having a factor < 50 digits is 0).
Now suppose we do a t55 and it fails to produce a factor
it means that if there is a 50-55 digit factor
probability that we missed it is 1/e. Using Bayes formula
we find that probability of having a 55 digits factor
is now (e^-1/11)/(e^-1/11+10/11) = 1/(10e+1) = 0.035.
But I don't see how this influences probability of N having
a 55-60 digit factor. One thing I thought about is using
the fact that t55 is equivalent to 0.2t60 hence
probability of missing a 55-60 digit factor is e^-0.2 (is it right?)
thus probability of having a 55-60 digits factors becomes
(e^-0.2/12)/(e^-0.2/12+11/12) = 1/(11e^0.2+1) = 0.069
Does that mean that the amount of ECM I should do before
~ 3150 curves @260e6 ?

Last fiddled with by YuL on 2015-06-05 at 10:19   2015-06-05, 11:13   #17
R.D. Silverman

Nov 2003

22×5×373 Posts Quote:
 Originally Posted by YuL Using Bayes formula we find that probability of having a 55 digits factor is now (e^-1/11)/(e^-1/11+10/11) = 1/(10e+1) = 0.035. But I don't see how this influences probability of N having a 55-60 digit factor.
The part you are missing is that a prior is already known. We already know
the probability of having a factor of a given size from Dickmans's fxn (or an
approximation such as Canfield-Erdos-Pomerance, or the approximation I give
in my paper) absent any information from ECM. You use my approximation

But:

ECM gives us additional information. The data can be turned into a sample density function.

Now apply Bayes' Thm. Convolve the prior with the sample density to derive a posterior density
function. Now use the expected value of that density function as the best guess for the size
of the unknown factor.   2015-06-05, 16:53   #18
bdodson

Jun 2005
lehigh.edu

210 Posts Quote:
 Originally Posted by R.D. Silverman The part you are missing is that a prior is already known. We already know the probability of having a factor of a given size from Dickmans's fxn (or an approximation such as Canfield-Erdos-Pomerance, or the approximation I give in my paper) absent any information from ECM. You use my approximation in your discussion above. But: ECM gives us additional information. The data can be turned into a sample density function. Now apply Bayes' Thm. Convolve the prior with the sample density to derive a posterior density function. Now use the expected value of that density function as the best guess for the size of the unknown factor.
Strange, but I don't recall having learned this during my undergrad math studies. Also seems
to be somewhat beyond amateur analysis/stat. Of course, I do recall years of re-reading the
Silverman-Wagstaff tables in the hardcopy you sent me in the early 80's; and trying to
understand the parameter revisions in Peter's thesis (hardcopy he sent on receiving his degree)
using more efficient step 2 (ecm/fft, before Paul's ecmnet project; with ever better step 2s).

But I'm reasonably sure that you'd agree we oughtn't to attempt extrapolation from reflexes
established while searching for p40s too far past searching for p45's; much less in to the p65's
of the OP's questions (cf. "pentium-p90-years for ever!"). So in RE your earlier post

Quote:
 GIVEN that the probability of missing a p55 was 1/e, what is the conditional probability of finding a factor between 55 and 60 digits? 60 and 65? 65 and 70? etc. This is what Bayes thm does for us.
could someone post a [*spoiler alert*] for how things look out here in p60-searches,
p65-searches (rather than p40/p45)?

As long as we're here, I was interested to see Sean's ecm count
Quote:
 My personal ECM effort for this number is: 114!+1 17900@110m, 10000@330m, 60000@850m, 5955@7600m ... I have also done similar effort of 115!+1.
which appears to be a complete t65 ("with ecm-6.3 parameters") followed by a switch to
optimal p75 parameters (skipping 2.9e9/p70). Seems to fit a new definition of a Most Wanted
number as getting t65+. -Bruce (somewhere past SNFS(27X))   2015-06-05, 17:16   #19
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by bdodson Strange, but I don't recall having learned this during my undergrad math studies.
I was very lucky. I got to take Bayesian stat from Howard Raiffa. (and Lindley visited U. of C
when I was a grad student there and taught a course)

If one uses the idea (associated with what Raiffa-Schleiffer calls post-posterior analysis IIRC)
of applying LOSS functions to the cost of making a wrong estimate (for a parameter), it is a theorem
that using the expected value of the posterior minimizes the unit-linear loss function.

Howard went through a proof of this theorem in class. IIRC it used a transformation to the characteristic
function of a density function(s), went through a little Fourier analysis on the convolution, then did a reverse
transform. I will see if I can find my old notes. I don't remember seeing a proof of this in print.   2015-06-05, 17:18   #20
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by bdodson But I'm reasonably sure that you'd agree we oughtn't to attempt extrapolation from reflexes established while searching for p40s too far past searching for p45's; much less in to the p65's of the OP's questions (cf. "pentium-p90-years for ever!").
Yes, we agree. But the theory should still apply in extending (say) a given p55 search to p60 or p65.

Also, the 2/9 rule of thumb is only an approximation. The value "2/9" should slowly decrease as the numbers get bigger
(because the likelihood of having an out-of-ECM-reach factor increases as the composites get larger)

Last fiddled with by R.D. Silverman on 2015-06-05 at 17:20 Reason: added sentence   2015-06-05, 23:25 #21 wblipp   "William" May 2003 New Haven 26×37 Posts I've got a draft analysis that says it would take four times as much work by ECM as to do the SNFS sieving. Even if correct, I don't think that answers the question. How should you include the post processing work? At the very least we should include the thread hours, but those aren't fungible with sieving thread hours.   2015-06-06, 08:22 #22 VictordeHolland   "Victor de Hollander" Aug 2011 the Netherlands 100100110002 Posts If anybody has a script which calculates the required ECM effort based on the N, (G/S)NFS size and ECM done, then I hold myself recommended :). Yes, I'm lazy! Last fiddled with by VictordeHolland on 2015-06-06 at 08:22   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post PawnProver44 Puzzles 10 2016-03-16 06:25 esqrkim Hardware 9 2010-03-02 20:27 Numbers Hardware 7 2005-09-12 19:10 tha Lone Mersenne Hunters 11 2004-05-17 15:43 sonjohan Software 2 2003-11-01 01:23

All times are UTC. The time now is 19:47.

Fri Oct 22 19:47:00 UTC 2021 up 91 days, 14:15, 0 users, load averages: 2.63, 2.81, 2.50