
View Poll Results: What is the largest EFF prize that GIMPS will ever receive?  
Out of Luck: 1 million digits  $50,000  0  0%  
10M digits  $100,000  4  10.81%  
100M digits  $150,000  11  29.73%  
Champions: 1 billion digits  $250,000  22  59.46%  
Voters: 37. You may not vote on this poll 

Thread Tools 
20060114, 21:58  #1 
Dec 2003
Hopefully Near M48
2·3·293 Posts 
Ultimate EFF Prize Limit of GIMPS
I'm curious to know some opinions about this. What is the largest of the EFF prizes (http://www.eff.org/awards/coop.php) that GIMPS will ever receive? An estimate of the discovery dates would also be appreciated. Any other relevant comments are welcome.

20060114, 22:35  #2 
Oct 2005
Fribourg, Switzerlan
374_{8} Posts 
It depends on too many factors :D
I hope it will be $250,000! 
20060114, 23:23  #3 
Mar 2004
101111101_{2} Posts 
Gimps found the last 8 largest primes, so it seems as if it will go on like that.
Fact is, that the number of mersenne primes is limited. It is easily possible that there is no mersenne prime with >10M decimal places less than M45000000. Now other primalty testing algorithms get more and more efficient. To find Sierpinskt and Proth primes with LLR (also based on George Woltmans code) is merely 1015% slower than a LucasLehmer. After reaching M38000000, it is possible that many people switch to Rieselsieve or Seventeen or Bust to test the smallest 10Mdigit numbers. Also the Generalized Fermat numbers are getting more and more interesting: staring around 3441463500^1048576 +1 or 11843670820000000000^524288 +1 gives many candidates with exactly 10 Million digits. There is some competition around. Any Predictions? 
20060119, 05:36  #4 
"Juan Tutors"
Mar 2004
1057_{8} Posts 
sorry if you said 1M, because considering the trend, and the massive support of this program, any less than 10M just makes no sense.
I said 100M, because I can seriously see myself testing 100M Mersennes for however many years it takes. Plus, there's no reason to believe that some nice improvements on the AKS test can't make it waayyyy faster. Plus, what if another randomized or absolutely polynomial time test appears that blows any of these tests off the map? 
20060119, 12:21  #5  
Nov 2003
2^{2}·5·373 Posts 
Quote:
ridiculous speculations? (1) No possible improvement of AKS can ever make it faster than LL. This is clear. (2) LL *IS* a polynomial time test. To prove N prime, it requires lg N multiplications mod N. Any test will require arithmetic mod N. The only issue is how to reduce the number of operations mod N or to speed the arithmetic. The multiplications used by LL run in nearly linear time. We will not do better. [note that it takes linear time just to write down the answer] (3) A Theorem of Pomerance shows, essentially that we can never hope to do better than O(lg N) multiplications in any test. All we might do is reduce the implied constant. His theorem places a bound on the size of a primality proof certificate. Although a rigorous proof is lacking, there are strong reasons to believe that LL is the fastest test that is theoretically possible. Now can we please stop this blathering about "blows these tests of the map"? 

20060119, 12:55  #6 
Aug 2002
Buenos Aires, Argentina
3·463 Posts 
Mersenne hunting is not done by performing LucasLehmer tests for all numbers of the form 2^p1 (p prime).
Instead, the project tries to find small factors using trial division and p1 in order to avoid the costly primality test. In this way about 60% of LL tests are not done. What is needed is a way to quickly eliminate candidates without necessarily finding factors. For example if instead of 40% we would have to perform only the 5% of LucasLehmer tests, the 10M prime should be found in relatively short time. Is there a theorem that prevents such a method? 
20060119, 21:28  #7  
∂^{2}ω=0
Sep 2002
República de California
2^{2}×3×7×139 Posts 
Quote:
Last fiddled with by ewmayer on 20060119 at 21:28 

20060119, 21:41  #8 
Aug 2002
Buenos Aires, Argentina
10101101101_{2} Posts 
I didn't say factoring. What I want is a probabilistic primality test faster than MillerRabin, useful even if it fails say 5% of the time (MR virtually does not fail in the 10Mdigit range). This would reduce about 10 times the number of candidates.

20060120, 05:32  #9 
"Juan Tutors"
Mar 2004
22F_{16} Posts 
Well is it possible that some other test is found for a number of a different form that, for a given size, is faster than the LL test?
Also, if someone says something ignorant, why not just save yourself the aneurysm sometimes? It's ok!! Some people aren't as smart as you!! 
20060120, 14:04  #10  
Nov 2003
2^{2}·5·373 Posts 
Quote:
being smart. The issue is doing one's homework. I assume that anyone sufficiently interested in a subject will do background reading before indulging in idle and ignorant speculation. And if one has NOT studied a subject, then, to quote Tom Lehrer, "The least he can do is to shut up" And, if you had bothered to read and understand my post, you would realize that I already asnswered the question you now ask. Although a formal proof is lacking, there is good reason to believe that no algorithm can be faster than LL for *any* number. Seeing the same ridiculous speculations over and over again about "faster primality tests" from people who are clearly clueless about the subject is TIRESOME. 

20060120, 14:44  #11  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Quote:
"Human nature" "Chance to push Silverman's 'hot button' again" Quote:
Quote:
some folks are insufficiently interested ... or "will do background reading" is not preciselyenough defined ... or your assumption is invalid. (For purposes of this discussion, I'll withhold comment on discernment of "indulging in idle and ignorant speculation".) Quote:
I once heard an interview in which Warren Buffett was quoted as replying, after having been asked what constituted wisdom, something like (this is my paraphrase) "Wisdom consists of having as many different models as possible, so that one may choose the most appropriate model to apply to any given situation." Last fiddled with by cheesehead on 20060120 at 14:58 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
The ultimate answer to life, rape, pregnancies, chemistry and everything  jasong  Soap Box  72  20120917 23:00 
The ultimate prime test ?  Carl Fischbach  Miscellaneous Math  33  20090911 20:49 
Ultimate gapbusting file  gd_barnes  Riesel Prime Search  26  20070723 15:23 
GIMPS' Prize.  T.Rex  Math  8  20070313 10:59 
Poll: Ultimate Limits of GIMPS  jinydu  Lounge  28  20051113 13:22 