> Conjecture time: The prime number earning the $150K prize will not be a
> Mersenne.
This isn't so much a conjecture as a prediction (there is a difference).
A conjecture is a very specialized prediction.
> Why do I say that? Even with processor speeds increasing, we have a good
> idea how long it'll take to find big primes by Lucas-Lehmer. Even for the
> 10M-digit prime it'll be a damn long time the way we are doing it now.
> Finding the monsters requires an intellectual leap by someone - possibly
> in processor design, more likely in number theory. Admittedly this leap
> may well be a better version of L-L in which case Mersennes will still be
> the record primes for a long while to come. But my hunch is that there is
> a better chance of finding some new way to either construct primes, or to
> test some other special-form number, than there is of dramatically
> improving on Lucas-Lehmer. Just a hunch. I might be wrong. I hope I live
> long enough to see all of the EFF prizes awarded, whether to Mersennes or
> not.
Ok, it seems doubtful that we will ever be able to find a test more efficient
than the LL test. The LL test involves p multiplications mod Mp, which is
pretty impressive. However, I agree with your prediction because there
are much more targeted types of numbers with similar running times (e.g.
Proth numbers). As Chris Nash pointed out, a Proth test would have taken
1/4th the time of the LL test on the Mersenne found in June on a number of
precisely 1,000,000 digits. You may be right about the construction of
prime numbers. Also if someone were to find a faster way to multiply than
an FFT convolution, that would dramatically improve primality testing.
> PS - On an unrelated note --- what is the smallest natural number that is
> not known whether it is prime or composite? Surely *someone* out there is
> trying to work from the bottom up and factor every number. (I don't know
> the answer. I am guessing the it is a smallish number of maybe 15 or
> so decimal digits?)
Probably the one right after the largest sieved interval. But I have
to ask the question: Who cares? Unless the larger sieved limit is
showcasing a new sieving algorithm, then why does it matter? To
verify the primality of numbers up to a hundred digits is a simple matter.
Just my $0.00 worth.
(the FSF's motto)
-Lucas
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
