Given that x^2 mod 2^p-1 can be computed very efficiently using DWT
(getting the remaindering operation for free), it occurs to me that
it ought to be possible to compute x^2 mod 2^p+1 just as efficiently,
using different "magic numbers". So, although Pepin's Test looks very
like Proth's Test (the only other difference is that using the base 3
is always sufficient for testing Fermat numbers), it _should_ be
possible to write an implementation of Pepin's Test that is about as
efficient as Prime95.
The problems are, of course, that there are going to be very few
Fermat numbers which can be tested in a "reasonable" time given
"current" hardware (by _any_ definition of the words quoted), and
that there is a very small chance that any of them will turn out to
be prime.
In case anyone else notices that F25 is an "interesting" size -
10,100,891 digits - could I save you a whole bundle of time by
remarking that F25, F26 and F27 are all known to be composite, we
know at least one factor of each of them. And F28 isn't quite big
enough to be worth $150K.
...............................................
On 30 Jul 99, at 11:26, Paul Landon wrote:
> Please don't be so quick to tell people to "FAQ Off"
Yes, I agree. Lots of replies like this on the list get irritating,
even to those of use who aren't the target of the abuse.
I suggest that those who feel it neccessary to reply in this vein do
so privately to the questionner, something along the lines of "There
is a FAQ at URL <> which answers your question : <quote from FAQ>"
The point here is that it keeps the list quieter, gives the
questionner the information they want and gently leads them to the
FAQ. And it's really no more effort than sending a "FAQ off" reply to
the list.
Regards
Brian Beesley
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
