Chris Nash <[EMAIL PROTECTED]> writes
>To: Prime Mailing List <[EMAIL PROTECTED]>
>Subject: Mersenne v Proth - help needed to improve Proth testing
>
>Hi folks
>
>Rhetorical question - why is the largest known prime a Mersenne and not a
>Proth prime? You'd think with the more places to look (more k values) you'd
>have good odds with Proth, but you don't. The Mersenne form 2^n-1 is
>simpler, yes, and means you can come up with some powerful results pretty
>simply. The obvious one is you only need to test Mersenne numbers where the
>exponent n is prime. Potential factors are of a very restricted form, 2kn+1.
Hi, Chris:
Because this issue is likely of interest to Mersenne searchers, as well,
I'm sending a copy of this to [EMAIL PROTECTED]
*** Top 10 reasons the largest known primes are Mersennes ***
(these are a bit longer, but hopefully less vapid than those on the
David Letterman show).
(Actually, I only came up with six, leaving four other slots for readers
of this list to fill for themselves):
10. Mersennes have a simpler form, hence are "sexier";
9. There are less Mersenne candidates in a given size range than Proths,
making it easier to exhaustively test a given range and move on to
the next-larger range. Thus, one is in the "nosebleed seats" (as it
were) much faster;
8. On the other hand (and in contrast to, say, Fermat numbers), there
are enough candidates in a given size range that one can easily
recruit many volunteers to run tests, and tell them honestly that
one of them has a very good chance of finding the next record prime.
For Fermat numbers, after F24 is done (a computation that doesn't
distribute well) there's F31, a monster which will not be feasible
for many years even on massively parallel hardware (F31 will take
roughly 2^14*31/24, or around 21,000 times as many machine operations
as F24, i.e. about 21,000 PPro200 CPU-years using the best current
algorithms. Thus, one could do it in around 2 years of 100% dedicated
CPU time on the latest 10,000-processor behemoth at Sandia labs,
assuming one could distribute the computation perfectly, and that
the U.S. government said "Sure, we're not really using the computer
for anything at the moment", both of which are just a tad unlikely).
After all that computing, you've still tested just ONE candidate for
primality. Assuming that for Fermats a similar percentage of candidates
in a given size range actually are prime as for Mersennes (about as
good an assumption as any given our current knowledge, you're much
less likely to find a prime for a given amount of CPU time this way.
(Of course, if either F24 or F31 were proved prime in the near future,
it would easily beat the largest known Mersenne prime.)
7. Even a child can understand the mechanics of the Lucas-Lehmer test,
which makes participation in something like the Great Internet Mersenne
Prime Search (GIMPS) attractive to a parent/teacher who want to foster
their children's interest in mathematics. In less than an hour, one
can explain the LL test to anyone who knows how to multiply and subtract:
To test if 2^p-1 is prime, start with the number 4, (or 10, or...).
Square and subtract 2. Do this p-2 times. If 2^p-1 divides the
result, it is prime.
Example 1: 2^3-1 = 7 is prime, since 7 divides (4^2-2)=14.
Example 2: 2^5-1 = 31 is prime, since 31 divides the last number
of the sequence: 4^2-2=14, 14^2-2=194, 194^2-2=37634.
Even showing that one can do the squaring modularly takes only
basic algebra. The kids can then do some other examples on a hand
calculator, then you tell them that they can run a program someone
wrote to do this test for really BIG numbers on the PC in the school
computer lab, and that they thus might be co-discoverer of the next
world record prime, and you get a pretty big gee whiz effect.
6. Because the current world record prime is a Mersenne, one has a
positive feedback mechanism: A. Getting lots of folks to test Mersennes
on their computers is easy because setting world records is appealing.
B. Because more CPU time (or even comparable CPU time - see (9) above)
is going into LL tests, it's more likely the next record prime will
be discovered this way. GO TO A.
5. All other things being equal (which they're not), three words:
Discrete Weighted Transform (R. Crandall and B. Fagin, Math. Comp. 62
(205), pp.305-324, January 1994). So far, this can only be used with
Mersenne and Fermat numbers. Being able to test a Mersenne number of
a given size 2-3 times faster (this is the typical speedup due to DWT)
than a Proth number of similar size means one can test more candidates
given the same amount of CPU time. Together with (9) and (6), I'd say
this makes it unlikely that the largest prime will be anything other
than a Mersenne in the near future, unless F24 happens to prove prime.
4.
3.
2.
1.
(Once others provide 4 more items (or more - we needn't discriminate
against non-powers-of-ten :), we can see if we can agree on an ordering
in terms of perceived importance.
None of this is meant to imply that the search for Proth primes is not
as (or more) interesting than that for Mersennes. It's mainly my take
on why Mersenne searching seems to have more mass appeal.
Regards,
Ernst
