mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2011-01-05, 14:07   #1
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5·359 Posts
Talking 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?


Christenson is offline   Reply With Quote
Old 2011-01-05, 14:15   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2×5×7×61 Posts
Default

Quote:
Originally Posted by Christenson View Post
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
Mini-Geek is offline   Reply With Quote
Old 2011-01-05, 17:28   #3
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

2·7·347 Posts
Default

Quote:
Originally Posted by Christenson View Post
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.
petrw1 is online now   Reply With Quote
Old 2011-01-05, 17:39   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by petrw1 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-01-05, 19:32   #5
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

12FA16 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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 :)
petrw1 is online now   Reply With Quote
Old 2011-01-05, 19:39   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by petrw1 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-01-06, 02:13   #7
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5×359 Posts
Default

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.
Christenson is offline   Reply With Quote
Old 2011-01-06, 02:19   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by Christenson View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-01-07, 03:39   #9
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

70316 Posts
Default

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.
Christenson is offline   Reply With Quote
Old 2011-01-07, 12:22   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Christenson View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-01-07, 14:50   #11
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

647410 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Why is TFing small numbers harder? casmith789 Information & Answers 4 2014-12-21 16:23
Use Msieve NFS for small numbers? skan Msieve 8 2013-02-26 20:35
ECM on small Mersenne Numbers Erich PrimeNet 16 2012-09-29 23:08
P-1 on small numbers Unregistered Information & Answers 2 2011-08-22 22:53
A new Strong Law of Small Numbers example cheesehead Math 7 2009-02-06 20:49

All times are UTC. The time now is 15:29.


Tue Dec 7 15:29:53 UTC 2021 up 137 days, 9:58, 1 user, load averages: 1.77, 1.61, 1.55

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.