20030228, 08:07  #1 
Feb 2003
19_{10} Posts 
Exponents < 2 Million
Since one of the other posts mention this range... I'll start a topic...
There has been considerable amount of ECM done in this range... particularly for exponents < 1 Million... Since many exponents have been ECM'd up to 25 digits... it would be useless to attempt to trialfactor them any higher than they already are... Why?? Although there is a minimal chance that ECM missed a factor... ECM'ing to 25 digits is the equivalent of trialfactoring to 2^83... Any exponent with ECM done to 25 digits is... therefore... essentially trialfactored higher than the 2^76 limit of Prime95... Exponents NOT ECM'd completely... or at all... to 25 digits... is of course the exception... Eric 
20030715, 18:10  #2 
"Richard B. Woods"
Aug 2002
Wisconsin USA
7692_{10} Posts 
For information on how much ECM factoring has already been performed for various 2^N1 and 2^N+1 which are not yet completely factored, see:
http://www.mersenne.org/ecmm.htm for 2^N1, N < 1200 http://www.mersenne.org/ecmp.htm for 2^N+1, N < 1200 http://www.mersenne.org/ecm1.htm for 2^P1, P prime and 1200 < P < 10000 http://www.mersenne.org/ecm2.htm for 2^P1, P prime and P > 10000 http://www.mersenne.org/ecmf.htm for Fermat numbers (2^N+1, N is a power of 2) 
20030716, 03:30  #3 
Mar 2003
New Zealand
1157_{10} Posts 
I thought that once the recommended amount of ECM has been done on an exponent for 25 digit factors, then there is still 1/e chance that a factor smaller than 25 digits remains. So trial factoring one of these exponents from 2^57 to 2^58 should have a 1/57e chance of finding a factor.
Geoff. 
20030716, 07:01  #4  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1111000001100_{2} Posts 
Quote:
Just as GIMPS discussions about factoring sometimes include statements like "You're wasting your time TFing past the Prime95 default powerof2 limit" or "There's no value in doing P1 to B1/B2 higher than those chosen by Prime95", which neglect to note that the Prime95 default limits are just points at which the efficiency of factorfinding by TF or P1 balance the efficiency of compositeproving by LL test, so too do ECM discussions sometimes make statements about the number of curves to be run with certain limits which are more absolute than is justified. What I have read is that the recommended numbers of ECM curves to run with certain limits are calculated to make the probability of finding a certainsizeorsmaller factor = 1  (1/e) = 63%. [Edit: See wblipp's more correct note, below, about "If you make "N" tests, each with probability of (1/N) of success, the probability of no successes is 1/e for large N"] They are NOT intended to signal that there is no point in running trial factoring for factors in that range. Quote:
If ECM had been done farther than that, such as to the limits recommended for factors of 25 digits or less, then TF from 2^57 to 2^58 would have a lower probability than 1/57e of finding an undiscovered factor.           Quote:
Quote:
Quote:
An exponent ECM'd to 25 digits is essentially 63% trialfactored to 2^83, with 37% of the potential factors below 2^83 not yet having been tried. Edit: note smh's comments below.    [Edited most of my paragraphs above to reduce the absolutization index of my own statements :) ] 

20030716, 11:33  #5  
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts 
Quote:
The chances of missing a 2^76 factor are lower then 37% But indeed there is still a small chance that a < 20 digit factor goes unnoticed. It's probably more efficient to run ECM with higher bounds on these numbers (with a good chance of finding larger factors) then continuing trail factoring to 2^60 or so 

20030716, 12:58  #6  
"William"
May 2003
New Haven
3·787 Posts 
Quote:
[code:1] digits D optimal B1 B2 expected curves N(B1,B2,D) 15 2e3 1.2e5 30 20 11e3 1.4e6 90 25 5e4 1.2e7 240 30 25e4 1.1e8 500 35 1e6 8.4e8 1100 40 3e6 4.0e9 2900 45 11e6 2.6e10 5500 50 43e6 1.8e11 9000 55 11e7 6.8e11 22000 60 26e7 2.3e12 52000 65 85e7 1.3e13 83000 70 29e8 7.2e13 120000[/code:1] I think this means that when testing with B1=25e4, if there is a 30 digit factor, there is a probability of 1/500 of finding on any particular test. Likewise, when testing at B1=1e6, if there is a 35 digit factor, there is a probability of 1/1100 of finding it on any particular test. Also, if you shifted from 24e4 to 1e6 after 500 curves at the lower level, and there is a 30 digit factor, the probability that you didn't find it during the 24e4 tests is 1/e. If there is a missed 30 digit factor, you will to continue to possibly find it during the 1e6 tests. What is the probability of finding that missed 30 digit factor in each 1e6 test? Does it remain at the 1/500 value it had during the 25e4 tests? Does it become the same as the 1/100 value for a 35 digit factor during these tests? Does it become even higher than 1/500 because more nearby numbers are smooth at this level? I suspect the last (higher than 1/500) is correct  if so, how do you calculate the new probability? 

20030716, 15:18  #7  
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts 
Quote:
Quote:
The latest GMP ECM client also has an option to increase the bound automatically after each curve. i think thats a more efficient way to find factors (of unknown size), but it makes it harder to keep track on the progress that has been made on a number 

20030716, 18:42  #8  
"William"
May 2003
New Haven
3×787 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Day Million  jasong  Puzzles  15  20070825 03:01 
73 million to 73.5 million to 2^63  DJones  Lone Mersenne Hunters  7  20070801 08:30 
Unreserving exponents(these exponents haven't been done)  jasong  Marin's Mersennearies  7  20061222 21:59 
GIMPS Credit for Exponents Between 79.3 Million and 596 Million  jinydu  Lounge  25  20061222 10:54 
2.2 million?  Prime95  PSearch  4  20030222 08:42 