Quote:
Originally Posted by ewmayer
it amounts to taking a Mersenne number N = M(p), then raising the seed B=3 to some "magic" obfuscated power which (using that \ is UBasic for "integer divide") equals
pow = floor(N/2) * floor(N/3).
E.g. for M(p) with p=3 this works out to floor(7/2) * floor(7/3) = 3*2 = 6. For general odd p, it simply amounts to an obfuscated way or writing N1. Thus, this is nothing more than a base3 Fermat pseudoprime test.

Actually, I was too hasty  it's even worse than I initially thought. The power actually being computed here is (N1)
^{2}/6, which (except for N=7, where this equals N1) is quadratic in N. E.g. for N=31, we're raising the initial seed tp the 150th power, rather than the 30th power required by the Fermat pseudoprime test.
I'll leave it as a homework exercise for the interested (and nonindolent) reader to answer the following:
a) Just how much slower is this (in an asymptotic largeN sense) than the Fermat PRP test? (Hint: it's slower, but not quadratically slower).
b) Since this computes a power which is actually a multiple of N1, is this in fact an even weaker pseudoprime test than the Fermat pseudoprime test?