Hi there Lucas...
> The reason is relativly clear: the work of checking *even one* factor of
> M(M(p)) is greater than the work required for an LL test on that number.
> This is because of the need for p squarings modulo some number greater
> than M(p).
Yes, however there is a rather curious combination of effects going on when
testing these numbers. To test if x is a factor of M(M(p)) requires p
squarings mod x, but p is a little less than log2(x). Admittedly, we're only
testing for factors, but there's a curious side effect of the test...
> prime, unless we find a factor. Interestingly enough, when we find the
next
> Mersenne prime, searching for a factor of M(M(p)) might allow us to find
an
> even bigger prime. If for example, 6*M(p)+1 divides M(M(p)), then it must
> be prime!
Oh, you can do much better than that... Let q=M(p), a prime. Now any factor
of M(q) is of the form 2kq+1. Provided 2kq+1<(2q+1)(2q+1), ie k<2q+2, if
2kq+1 divides M(q), then 2kq+1 is prime. In theory then this sort of factor
test can prove the primality of a number up to TWICE THE SQUARE of M(p), yet
the proof still only requires only p squaring operations (admittedly, to a
slightly less pleasant modulus, but readily optimizable). Of course, the
downside is, one has no idea how far you'd need to search (or even if such a
number exists, M(M(p)) could be prime and you'd never know it) - the upside
is, you might get lucky very quickly...
> Wait, that might just be the reason to search! Will only searched up to
> k=4 for M(M(6972593)), but if 2*k*M(p)+1 divides M(M(p)), then you've just
> beaten the world record! Non-Mersenne's might once again grace the top
> 10 list!
Steady on, there are a few non-Mersennes hanging on in there :) But this
form is very reminiscent of the Miller/Wheeler record (the first one of the
electronic age), 180.M(127)^2+1. I for one wouldn't object to dedicating a
few cycles here and there to find a factor of M(M(1257787)) and who knows,
find the largest known non-GIMPS prime...
Chris
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
