mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-06-01, 15:25   #12
wreck
 
wreck's Avatar
 
"Bo Chen"
Oct 2005
Wuhan,China

2×5×17 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
"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.
wreck is offline   Reply With Quote
Old 2015-06-01, 16:02   #13
YuL
 
YuL's Avatar
 
Feb 2012
Paris, France

7·23 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
"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
YuL is offline   Reply With Quote
Old 2015-06-01, 16:35   #14
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by YuL View Post
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....
R.D. Silverman is offline   Reply With Quote
Old 2015-06-04, 21:13   #15
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

17·563 Posts
Default

Quote:
Originally Posted by YuL View Post
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!
Batalov is offline   Reply With Quote
Old 2015-06-05, 10:17   #16
YuL
 
YuL's Avatar
 
Feb 2012
Paris, France

7×23 Posts
Default

Quote:
Originally Posted by Batalov View Post
...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 View Post
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
switching to NFS is 7% of 45000 thread.hour = 3150 thread.hour
~ 3150 curves @260e6 ?

Last fiddled with by YuL on 2015-06-05 at 10:19
YuL is offline   Reply With Quote
Old 2015-06-05, 11:13   #17
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by YuL View Post
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.

<snip>
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-06-05, 16:53   #18
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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))
bdodson is offline   Reply With Quote
Old 2015-06-05, 17:16   #19
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by bdodson View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-06-05, 17:18   #20
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by bdodson View Post

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
R.D. Silverman is offline   Reply With Quote
Old 2015-06-05, 23:25   #21
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

26×37 Posts
Default

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.
wblipp is offline   Reply With Quote
Old 2015-06-06, 08:22   #22
VictordeHolland
 
VictordeHolland's Avatar
 
"Victor de Hollander"
Aug 2011
the Netherlands

100100110002 Posts
Default

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
VictordeHolland is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Switching digits test PawnProver44 Puzzles 10 2016-03-16 06:25
Switching computers esqrkim Hardware 9 2010-03-02 20:27
Switching Boxes Numbers Hardware 7 2005-09-12 19:10
switching to doublechecking tha Lone Mersenne Hunters 11 2004-05-17 15:43
switching PC's for same exponent 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

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.