FermatPRP vs. M-R

[Paul Leyland]

On Wed, 2011-03-16 at 14:47 +0000, James Wanless wrote:
> Hi Paul,
> Thanks for your email.
> I've had this discussion w/ a number of people now - at some point I'm  
> hoping people are going to start catching on, and I can stop banging  
> on about it... so if you (out there) agree w/ me - _please_ let us all  
> know so I can rest easy!!! :)

Either I don't understand what you are trying to say or I disagree with
your statements.

> > 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.
> 
> That is true. And that's what I mean by M-R working better in the  
> wrong direction. BUT this is not what we need to know from a probable  
> prime test.

Let me try rephrasing.

For a given value of N to be tested and for a chosen uniformly and at
random in the range 2 < a < N-1, let P_F(a,N) be the probability that
the Fermat test correctly states that N is prime.  Let P_M(a,N) be the
probability that the M-R test correctly states that N is prime.  It is a
theorem that P_F(a,N) <= P_M(a,N).

That theorem, to me, captures the notion that M_R is a more accurate
primality test than Fermat.  Neither are perfect tests because each can
fail but the former fails less often than the latter.

Paul