FermatPRP vs. M-R

[Paul Leyland]

On Wed, 2011-03-16 at 10:17 +0000, James Wanless wrote:
> (Seems I sent this from my wrong email address first :)
> 
> In case you're wondering ;-)
> M-R calculates its probabilities in the wrong (reverse) direction to what
> one needs.

What do you mean by this statement?

> Is there a (simple) FermatPRP currently implemented in GMP?
> 
> I ask because FermatPRP is more accurate than M-R.

And what the heck does this mean?  Either we disagree on the definition
of "FermatPRP" or we disagree on the meaning of "more accurate".

If "FermatPRP" means checking that a^(n-1) == 1 (mod n) and then stating
that n has not been proved to be composite, we disagree on "more
accurate".  For a given value of a, ALL values of n which the M-R test
to base a fails to prove composite will also be failed to be proved
composite by the FermatPRP.  The converse is not true.  There are values
of n which will be proved composite by MR but not by FermatPRP.  The
Carmichael numbers are examples.  I would state that M-R is "more
accurate" because it is a more reliable distinguisher of composites than
is FermatPRP.

Paul