20110105, 14:07  #1 
Dec 2010
Monticello
5×359 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? 
20110105, 14:15  #2  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
2^{2}×11×97 Posts 
Quote:
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 allheads 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 allheads. If you do it long enough, it should average out to 256 tosses between allheads, 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 MiniGeek on 20110105 at 14:21 

20110105, 17:28  #3  
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
12A3_{16} Posts 
Quote:
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 P1 which in turn depend on how many bit levels for TF and how big the B1/B2 were for P1. Last fiddled with by petrw1 on 20110105 at 17:31 Reason: Last 2 paragraphs. 

20110105, 17:39  #4  
Nov 2003
2^{2}·5·373 Posts 
Quote:
(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. 

20110105, 19:32  #5  
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
11243_{8} Posts 
Quote:
I would like to do more reading on these topics. I just need to "make" the time for it. Quote:
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:
Quote:
Quote:
Quote:
Last fiddled with by petrw1 on 20110105 at 19:33 Reason: Spelign :) 

20110105, 19:39  #6  
Nov 2003
2^{2}·5·373 Posts 
Quote:
form or congruence class) for ECM for 1 curve is exactly the same as it is for P1. Think of P1 as a faster way of doing just one (specific!) elliptic curve. Quote:
Quote:
my paper discusses this. Quote:


20110106, 02:13  #7 
Dec 2010
Monticello
5·359 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 P1 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 fourorfive dimensional problem which involved a leastsquares 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 doublecabinet about 6 feet high on a raised floor. 
20110106, 02:19  #8  
Nov 2003
7460_{10} Posts 
Quote:
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. 

20110107, 03:39  #9 
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. 
20110107, 12:22  #10 
Nov 2003
16444_{8} Posts 

20110107, 14:50  #11 
"Lucan"
Dec 2006
England
14512_{8} Posts 
Have you read my paper (written with Lord Lucan)
entitled "The Small Law of Strong Numbers"? David Last fiddled with by davieddy on 20110107 at 14:51 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Why is TFing small numbers harder?  casmith789  Information & Answers  4  20141221 16:23 
Use Msieve NFS for small numbers?  skan  Msieve  8  20130226 20:35 
ECM on small Mersenne Numbers  Erich  PrimeNet  16  20120929 23:08 
P1 on small numbers  Unregistered  Information & Answers  2  20110822 22:53 
A new Strong Law of Small Numbers example  cheesehead  Math  7  20090206 20:49 