> > Someone asked if there could be a better method for testing
> > Mersenne numbers
> > than the L-L test. I think that the L-L test is essentially
> > as efficient as
> > possible. However, I think that there is room for improvement in the
> > algorithms for doing the arithmetic involved.
>
> That is a remarkably bold claim. It's akin to saying that the only way of
> finding primes is by brute force testing of all candidates.
How about a clever method of computing just the last few bits of
the residual - if we could work mod 2^64 instead of mod 2^p-1 then
that would give essentially a *huge* speed increase, even if the
algorithm was a great deal more complex.
Of course, there is still (approx) 1 chance in 1.8E19 (2^64) that the whole
residual is non-zero even though the low-order 64 bits are zero, so,
in the rare event we computed Res64 = 0, we'd still have to run a
full LL test.
Also, if you can find quicker arithmetic algorithms, then *please*
get in touch with Donald Knuth! There may be some (fairly small)
scope for improvement in the implementation - but, to get a major
advance, we're going to need dedicated hardware. I believe the
Chudnovskys (apologies if I've misspelled their name) had
dedicated hardware that could do a 2^20 bit by 2^20 bit
multiplication in less than a microsecond, about 15 years ago.
(Reference, "The Joy of Pi") That sort of raw power would be
*exceedingly* useful for LL testing, but is unlikely to find its way
into consumer products - unless someone can think of a "killer
application" that would make hardware implementation of this sort
of instruction essential!
> To me, at least, it is conceivable that some advance in number theory will
> prove that there is a finite number of Mersenne primes and that their values
> are given by a relatively simple formula.
I agree... except I'd replace "and" by "and/or".
In any event, I don't think the proof will fit in the margin of this
e-mail ;->
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
