mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

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

Reply
 
Thread Tools
Old 2006-01-14, 21:58   #1
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2·3·293 Posts
Default 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.
jinydu is offline   Reply With Quote
Old 2006-01-14, 22:35   #2
victor
 
victor's Avatar
 
Oct 2005
Fribourg, Switzerlan

3748 Posts
Default

It depends on too many factors :D

I hope it will be $250,000!
victor is offline   Reply With Quote
Old 2006-01-14, 23:23   #3
biwema
 
biwema's Avatar
 
Mar 2004

1011111012 Posts
Default

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?
biwema is offline   Reply With Quote
Old 2006-01-19, 05:36   #4
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

10578 Posts
Default

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?
JuanTutors is offline   Reply With Quote
Old 2006-01-19, 12:21   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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
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"?
R.D. Silverman is offline   Reply With Quote
Old 2006-01-19, 12:55   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

3·463 Posts
Default

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?
alpertron is offline   Reply With Quote
Old 2006-01-19, 21:28   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

22×3×7×139 Posts
Default

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
ewmayer is offline   Reply With Quote
Old 2006-01-19, 21:41   #8
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101011011012 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2006-01-20, 05:32   #9
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

22F16 Posts
Default

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!!
JuanTutors is offline   Reply With Quote
Old 2006-01-20, 14:04   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2006-01-20, 14:44   #11
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

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

your assumption is invalid.

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

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 2012-09-17 23:00
The ultimate prime test ? Carl Fischbach Miscellaneous Math 33 2009-09-11 20:49
Ultimate gap-busting file gd_barnes Riesel Prime Search 26 2007-07-23 15:23
GIMPS' Prize. T.Rex Math 8 2007-03-13 10:59
Poll: Ultimate Limits of GIMPS 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

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.