"New primality proving test from Alex Petrov"

[ewmayer]

Originally Posted by m_f_h

I think the sequence A049062 and the first comment to it explains everything, don't you agree ?
(Odd terms of this sequence are exactly Petrov's exceptions.)

Yes - I didn't look at it closely the first time, because your first post about it above only highlighted a few of Petrov's exceptions.

Anyway, I think we've beaten this to death, now -- let's briefly summarize:

1) It's apparently a rediscovery of a known PRP test;
2) No more efficient than other PRP tests (C&P cite a factor 2x slower than e.g. base-Q Fermat PRP test);
3) Main usefulness may be that when combined with e.g. a single base-Q Fermat PRP test, it seems to allow very few composites to slip through, and apparently no Carmichael-style composites, i.e. the Fibonacci pseudoprime test is in some sense "nearly orthogonal" to the Fermat test.

With respect to (3), C&P cite specifically only the case Q=2 -- it would be interesting to see whether the false-prime statistics for other Q are similar, or whether are any particular small value of Q that give especially few false primes (or none up to an especially high bound). The Carmichael-number aspects of this are also potentially interesting.

Homework assignment for the interested there...perhaps someone could do a more thorough literature search to see what work has already been done in this area.