FermatPRP vs. M-R

[James Wanless]

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!!! :)
J

On 16 Mar 2011, at 14:27, Paul Leyland wrote:

> 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.

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.

>  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
>
>