> 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.
> 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.
That bit is virtually free of charge. Any quadratic non-residue will do just
fine. If a^(n-1)/2 isn't -1, then the number isn't prime (by Euler's
quadratic residue criterion). The algorithm does take longer, sure, but it's
the targetability that makes the difference. If the first 10^7+ digit prime
has 20 million digits, it'll be taking longer to test each one than a 10
million digit Proth candidate.
I'm playing devil's advocate here. If prize money is anybody's motivation,
we'd all be better off selling our PC's and buying lottery tickets, or
hitting the stock market.
Chris
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
