View Single Post
Old 2006-10-20, 03:04   #7
ewmayer's Avatar
Sep 2002
Rep├║blica de California

2D3D16 Posts

Originally Posted by ewmayer View Post
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 N-1. Thus, this is nothing more than a base-3 Fermat pseudoprime test.
Actually, I was too hasty -- it's even worse than I initially thought. The power actually being computed here is (N-1)2/6, which (except for N=7, where this equals N-1) 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 non-indolent) reader to answer the following:

a) Just how much slower is this (in an asymptotic large-N 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 N-1, is this in fact an even weaker pseudoprime test than the Fermat pseudoprime test?
ewmayer is offline   Reply With Quote