# FermatPRP vs. M-R

James Wanless james at grok.ltd.uk
Wed Mar 16 15:47:00 CET 2011

```Hi Paul,
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
>
>

```