mersenneforum.org Ultimate EFF Prize Limit of GIMPS
 Register FAQ Search Today's Posts Mark Forums Read

 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

 2006-01-14, 21:58 #1 jinydu     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.
 2006-01-14, 22:35 #2 victor     Oct 2005 Fribourg, Switzerlan 3748 Posts It depends on too many factors :D I hope it will be \$250,000!
 2006-01-14, 23:23 #3 biwema     Mar 2004 1011111012 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 10-15% 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?
 2006-01-19, 05:36 #4 JuanTutors     "Juan Tutors" Mar 2004 10578 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?
2006-01-19, 12:21   #5
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by dominicanpapi82 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?
What is it that compels people who know NOTHING about a subject to make
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
(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

 2006-01-19, 12:55 #6 alpertron     Aug 2002 Buenos Aires, Argentina 3·463 Posts Mersenne hunting is not done by performing Lucas-Lehmer tests for all numbers of the form 2^p-1 (p prime). Instead, the project tries to find small factors using trial division and p-1 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 Lucas-Lehmer tests, the 10M prime should be found in relatively short time. Is there a theorem that prevents such a method?
2006-01-19, 21:28   #7
ewmayer
2ω=0

Sep 2002
República de California

22×3×7×139 Posts

Quote:
 Originally Posted by alpertron 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 Lucas-Lehmer tests, the 10M prime should be found in relatively short time. Is there a theorem that prevents such a method?
No theorem, but it is generally believed that factoring is a "hard" problem, so it is exponentially more difficult to find factors <= N digits as N increases. The hard part in what you propose is not finding factors of more Mersenne numbers - that we can do if we simply expend more factoring effort - the hard part is doing so sufficiently cheaply to make it worth our while. To eliminate as large a fraction of M(p) as you mention would require oders-of-magnitude speedups in any or all of: sieving, p-1, and ecm, or a new class of factoring algorithm that is asymptotically faster (though it's still going to be exponential) than these for finding small factors of large input numbers. Such breakthroughs don't grow on trees.

Last fiddled with by ewmayer on 2006-01-19 at 21:28

 2006-01-19, 21:41 #8 alpertron     Aug 2002 Buenos Aires, Argentina 101011011012 Posts I didn't say factoring. What I want is a probabilistic primality test faster than Miller-Rabin, useful even if it fails say 5% of the time (MR virtually does not fail in the 10M-digit range). This would reduce about 10 times the number of candidates.
 2006-01-20, 05:32 #9 JuanTutors     "Juan Tutors" Mar 2004 22F16 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!!
2006-01-20, 14:04   #10
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by dominicanpapi82 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!!
The issue is not intelligence, or lack thereof. It has NOTHING to do with
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.

2006-01-20, 14:44   #11

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

Quote:
 Originally Posted by R.D. Silverman What is it that compels people who know NOTHING about a subject to make ridiculous speculations?
"Curiosity"

"Human nature"

"Chance to push Silverman's 'hot button' again"

Quote:
 The issue is doing one's homework.
No, that's not the issue. (For details, inquiring readers may do a search on "homework" in the Math subforum to find my earlier exposition.)

Quote:
 I assume that anyone sufficiently interested in a subject will do background reading before indulging in idle and ignorant speculation.
So, either

some folks are insufficiently interested ... or

"will do background reading" is not precisely-enough defined ... or

(For purposes of this discussion, I'll withhold comment on discernment of "indulging in idle and ignorant speculation".)

Quote:
 And if one has NOT studied a subject, then, to quote Tom Lehrer, "The least he can do is to shut up"
You're fond of rules for situations in which one person is the authority figure, aren't you ... even in more open situations where you don't really have authoritarian control over others.

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 2006-01-20 at 14:58

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Soap Box 72 2012-09-17 23:00 Carl Fischbach Miscellaneous Math 33 2009-09-11 20:49 gd_barnes Riesel Prime Search 26 2007-07-23 15:23 T.Rex Math 8 2007-03-13 10:59 jinydu Lounge 28 2005-11-13 13:22

All times are UTC. The time now is 18:24.

Sun Dec 5 18:24:43 UTC 2021 up 135 days, 12:53, 1 user, load averages: 1.57, 1.63, 1.63