mersenneforum.org Strong Law of Small Numbers?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2011-01-05, 14:07 #1 Christenson     Dec 2010 Monticello 34038 Posts Strong Law of Small Numbers? Ladies and Gentlemen: I've set some of my CPU cores to ECM factoring relatively small numbers (M800K or so) and noticed that it takes about 20 GHz days each time (and about 250 exponents) to actually find a factor. My question is, does this generalize, (for small ranges of exponents, the ones that will be factored by a given size ECM curve follow a regular pattern) or is it an example of the law of small numbers, where there are more properties to be conjectured than the numbers can support? Does anyone else have a similar experience?
2011-01-05, 14:15   #2
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2·5·7·61 Posts

Quote:
 Originally Posted by Christenson I've set some of my CPU cores to ECM factoring relatively small numbers (M800K or so) and noticed that it takes about 20 GHz days each time (and about 250 exponents) to actually find a factor. My question is, does this generalize, (for small ranges of exponents, the ones that will be factored by a given size ECM curve follow a regular pattern) or is it an example of the law of small numbers, where there are more properties to be conjectured than the numbers can support? Does anyone else have a similar experience?
Where we don't know the size of the factors in advance, it's basically a random distribution as to what exponents have factors in a certain digit range. If you are, as I think you're saying, seeing a consistent separation of about 250 exponents between discoveries, I'd say that's definitely just a coincidence. The average might, in theory, really be about 250, (and given the composite cofactor size and ECM bounds you could calculate this) so you could expect that to be the average separation, but you'd only expect a certain percentage of them to be, say, 200-300 exponents away from the last one. They could be (roughly) evenly spaced, or all in bunches, or hardly any at all, but that doesn't mean it's still not basically random.
I'm not sure I'd call it an effect of the law of small numbers, perhaps just humans seeing patterns in random data where none truly exist.
It's a bit like flipping a coin eight times, or tossing out eight coins randomly, and seeing if they all are heads. The chance of this, assuming perfectly fair coins, is 1/256, so you can expect to get one all-heads for every 256 times you toss the coins. But when you actually do it, you could have 10, or 250, or 792 tosses between two times that you get all-heads. If you do it long enough, it should average out to 256 tosses between all-heads, but each toss is still an independent random event, just like running a certain number of ECM curves on a certain exponent.

Last fiddled with by Mini-Geek on 2011-01-05 at 14:21

2011-01-05, 17:28   #3
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

486210 Posts

Quote:
 Originally Posted by Christenson Ladies and Gentlemen: I've set some of my CPU cores to ECM factoring relatively small numbers (M800K or so) and noticed that it takes about 20 GHz days each time (and about 250 exponents) to actually find a factor. My question is, does this generalize, (for small ranges of exponents, the ones that will be factored by a given size ECM curve follow a regular pattern) or is it an example of the law of small numbers, where there are more properties to be conjectured than the numbers can support? Does anyone else have a similar experience?
As I posted here: http://www.mersenneforum.org/showthread.php?t=14522
I have so far 802 ECM attempts and 11 factors (about 1 in 72).

Another user (XYZZY) was 1 out of 47.

But also as I go on to say I would rather have an idea of factors expected per curve. Most of my attempts were 3 curves each though a few were 1 and some were close to 50 curves. Obviously if all my attempts were 50 curves per exponent I'd have a lot more than 11 factors. As it stands for me I'd estimate my average number of curves per exponent is still close to 3 so I have 1 factor per about 210 curves.

Oh and almost all of my ECM is in the 300M and 500M ranges.

And one more thing: the odds that ECM finds a factor also depends on mow many were first found by TF or P-1 which in turn depend on how many bit levels for TF and how big the B1/B2 were for P-1.

Last fiddled with by petrw1 on 2011-01-05 at 17:31 Reason: Last 2 paragraphs.

2011-01-05, 17:39   #4
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by petrw1 As I posted here: http://www.mersenneforum.org/showthread.php?t=14522 I have so far 802 ECM attempts and 11 factors (about 1 in 72). Another user (XYZZY) was 1 out of 47. But also as I go on to say I would rather have an idea of factors expected per curve. Most of my attempts were 3 curves each though a few were 1 and some were close to 50 curves. Obviously if all my attempts were 50 curves per exponent I'd have a lot more than 11 factors. As it stands for me I'd estimate my average number of curves per exponent is still close to 3 so I have 1 factor per about 210 curves. Oh and almost all of my ECM is in the 300M and 500M ranges. And one more thing: the odds that ECM finds a factor also depends on mow many were first found by TF or P-1 which in turn depend on how many bit levels for TF and how big the B1/B2 were for P-1.
Go read two references.

(1) Knuth, vol 2. Look up "Dickman's Function"
(2) Read my joint paper with Sam Wagstaff: A Practical Analysis of ECM.

BTW, I have read what you have posted. Several times in fact. What you
state is very very vague. Please state precisely the exact question you
are trying to ask.

Whether ECM finds a factor of a very large number depends on a number
of things:

(1) The extent to which the number has already been subjected to a search
for small factors.

(2) The step 1, step 2 limits you use for ECM.

(3) The number of curves you run.

(4) Oddly enough, if you are searching for a factor p of a very large number
N, and no prior information about its factors is known, then the probability
of finding a factor p , x < p < x^2 of N, is almost exactly 1/2 provided
that x is not too big relative to N. Note that the result is independent of the
size of N and independent of the value of x.

2011-01-05, 19:32   #5
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

2×11×13×17 Posts

Quote:
 Originally Posted by R.D. Silverman Go read two references. (1) Knuth, vol 2. Look up "Dickman's Function" (2) Read my joint paper with Sam Wagstaff: A Practical Analysis of ECM.
Thanks
I would like to do more reading on these topics.
I just need to "make" the time for it.

Quote:
 BTW, I have read what you have posted. Several times in fact. What you state is very very vague. Please state precisely the exact question you are trying to ask.
I wasn't so much asking a question as I was trying to provide a response to the Christenson.
Though I did have a request that I presented in the Factoring Forum: an option to report ECM success per curve instead of per run; since a run can have any number of curves --- I've seen anywhere from 1 to 1,000). Barring that I'd just be curious to know how to compute the odds. I suspect the answer is in the articles you quoted above.
Quote:
 Whether ECM finds a factor of a very large number depends on a number of things: (1) The extent to which the number has already been subjected to a search for small factors.
That is one point I made in my previous post: i.e how much TF or P-1 has been done.
Quote:
 (2) The step 1, step 2 limits you use for ECM.
I use the published limits on the ECM status page.
Quote:
 (3) The number of curves you run.
Understood --- I've done anywhere from 1 to 50
Quote:
 (4) Oddly enough, if you are searching for a factor p of a very large number N, and no prior information about its factors is known, then the probability of finding a factor p , x < p < x^2 of N, is almost exactly 1/2 provided that x is not too big relative to N. Note that the result is independent of the size of N and independent of the value of x.
I seem to recall reading that somewhere before.

Last fiddled with by petrw1 on 2011-01-05 at 19:33 Reason: Spelign :)

2011-01-05, 19:39   #6
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by petrw1 Thanks I would like to do more reading on these topics. I just need to "make" the time for it. I wasn't so much asking a question as I was trying to provide a response to the Christenson. Though I did have a request that I presented in the Factoring Forum: an option to report ECM success per curve instead of per run;
The probability (for a number whose factors do not conform to some known
form or congruence class) for ECM for 1 curve is exactly the same as it
is for P-1. Think of P-1 as a faster way of doing just one (specific!)
elliptic curve.

Quote:
 since a run can have any number of curves --- I've seen anywhere from 1 to 1,000). Barring that I'd just be curious to know how to compute the odds. I suspect the answer is in the articles you quoted above.
My paper describes it in detail.

Quote:
 That is one point I made in my previous post: i.e how much TF or P-1 has been done.
One then uses Bayes' Theorem to compute the posterior odds. Again,
my paper discusses this.

Quote:
 I seem to recall reading that somewhere before.
This also comes from my paper.

 2011-01-06, 02:13 #7 Christenson     Dec 2010 Monticello 179510 Posts Thanks all....it seems like I'm flipping coins (by running Primenet assigned sets of 3 ECM curves with a particular memory limit) particularly well this month, and that it's not a good bet that the pattern will continue. I assume prior Primenet TF and P-1 tests had already not found factors within reasonable limits, or I wouldn't have the assignment at hand. What I was remembering was a certain four-or-five dimensional problem which involved a least-squares fit of 35 or so observed radioactive decay data to the half lives of the two isotopes involved, which I had solved many years ago by steepest descent. Once the fit got reasonable, I found that there were many small twists and turns in the vectors that were going in the direction of steepest descent, but that if you took the average over a reasonable number of them and guessed that in that direction was more descent, the global minimum was reached reasonably quickly. This was in the days of the VAX, when it sat in a double-cabinet about 6 feet high on a raised floor.
2011-01-06, 02:19   #8
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by Christenson Thanks all....it seems like I'm flipping coins (by running Primenet assigned sets of 3 ECM curves with a particular memory limit) particularly well this month, and that it's not a good bet that the pattern will continue. .
Stop this. I mean no insult but talking about "the pattern" in what is
conjectured to be randomly distributed it makes you sound like a crank.

It's a mistake amateurs and cranks make all the time: seeing some
imagined "pattern". People are very good at seeing patterns that are
not there.

 2011-01-07, 03:39 #9 Christenson     Dec 2010 Monticello 5·359 Posts Mr Silverman: Lighten up! I left at least two grins out of the last post. Two sixes in a row from two rolls of the dice is a pattern, but 5 times out of six it won't continue on the third throw of a fair die. If I begin the thread by wondering whether what is happening on an extremely small sample generalizes, and with a humourous picture of Bart simpson writing sentences on the blackboard about dumb questions, then I'm acutely aware of just how shaky the ground under my feet is when I speak of a "pattern" and very much expecting to find myself all wet. The sample, incidentally is over around 550 trials with successes around trial #250 and #500) ....and it's exactly what I meant when I said I must be doing a particularly good job of flipping coins this month. And yes, I'm an amateur...I've got a day job, it's called engineering, and my employer thinks I'm awfully good at it.
2011-01-07, 12:22   #10
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Christenson And yes, I'm an amateur...I've got a day job, it's called engineering, and my employer thinks I'm awfully good at it.
Excellent!

Don't make the mistake of believing that expertise in one technical field
conveys expertise in another.

 2011-01-07, 14:50 #11 davieddy     "Lucan" Dec 2006 England 2·3·13·83 Posts Have you read my paper (written with Lord Lucan) entitled "The Small Law of Strong Numbers"? David Last fiddled with by davieddy on 2011-01-07 at 14:51

 Similar Threads Thread Thread Starter Forum Replies Last Post casmith789 Information & Answers 4 2014-12-21 16:23 skan Msieve 8 2013-02-26 20:35 Erich PrimeNet 16 2012-09-29 23:08 Unregistered Information & Answers 2 2011-08-22 22:53 cheesehead Math 7 2009-02-06 20:49

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

Wed Dec 8 21:10:41 UTC 2021 up 138 days, 15:39, 1 user, load averages: 1.79, 1.49, 1.54