Mersenne: Base-3 Pseudoprimes

[Dave Mullen]

I was wondering if base-3 pseudo-prime testing might be considerably faster than LL testing for Mersenne Primes ?   The base-3 pseudo-prime test is defined as :-   3 ^ P == 3 (mod P) where P is a probable-prime (base-3 prp) 3 ^ P <> 3 (mod P) where P is composite   We know that using binary exponentiation saves having to calculate every power of 3, just some intermediates and the final required answer ...   e.g. For M(3) = 7, (111 in binary), starting with the value 3, square, multiply by 3, square, multiply by 3   This is effectively 4 multiplys to get our answer.   If we used this modified form of the test :-   3 ^ (P+1) == 9 (mod P)   then we'd only need 3 multiplys i.e. starting with value 3, square, square, square.   This situation improves with higher exponents i.e. M(13) = 8191, (1111111111111 in binary).   Usual method takes 24 multiplys, modified method only takes 13 multiplys.   i.e.for a given Mersenne Exponent, usual method takes (Exp * 2) - 2 multiplies, modified method takes (Exp) multiplys.   Now, okay, this is still 2 more multiplys than the LL test would take. But I believe there must be some advantages.   1) For the LL test using FFT multiplys, we have to Transform the data, Multiply the matrices, Inverse Transform the data, then subtract 2. I am assuming that the only reason we do the Forward and Inverse Transform each time is so we can subtract the 2 ? Please correct me here if I'm wrong !   (by the way, I would appreciate some pointers to FFTs for large integer multiplication for idiots - I understand the (very) basic concept, but how does the modulus occur automatically, why do we need to scramble the data, why does it all work etc.)   2) If we are doing base-3 prps, the only operation we need is multiply - so therefore we Transform the start value 3, then multiply the matrix by itself as many times as required, then finally do one Inverse Transform. This must save a lot of time over traditional LL testing, all those Transforms jumping in and out of virtual memory (a lot of us don't have 128+ MB of RAM !!).   3) The base-3 prp does not prove primality 100%, but it does prove compositeness. So we might narrow down our range of potential Mersenne exponents more quickly. And if if turns out that when we test the remaining exponents, the LL test fails - what the hell, we just found a new Carmichael Number - might still be a new record !!   Dave