On 25 Jul 99, at 16:40, Jeff Woods wrote:
> While I agree with this, if the effort does NOT fragment and jump ahead to
> potential 10MM-digits, someone else is likely to find and claim that $100K
> with a Proth prime, since checking those will take far less time than a
> Mersenne test of the same order.
Eh?
Proth's Test for n = k*2^m+1 says that there exists a such that
a^(n-1)/2 + 1 is divisible by n.
This takes m-1 squarings modulo n to evaluate, in the same way that
the Lucas-Lehmer test takes p-2 iterations. So the work volume looks
similar. (The LL test "subtract 2" step costs so little that we can
disregard it, for the purposes of estimating run time.)
But, it's harder to work modulo k*2^m+1 than it is to work modulo
2^p-1, and could certainly not be made cheaper computationally than
the "magic number" method in the DWT, which enables us to work modulo
2^p-1 essentially free of charge.
The other factor in evaluating this is that, in Proth's Test, a has
got to be an odd prime - if you pick the wrong prime, you're wasting
time, though fortunately this can usually be detected very early.
Regards
Brian Beesley
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
