FermatPRP vs. M-R
james at grok.ltd.uk
Wed Mar 16 15:47:00 CET 2011
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!!! :)
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
> of "FermatPRP" or we disagree on the meaning of "more accurate".
> If "FermatPRP" means checking that a^(n-1) == 1 (mod n) and then
> 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
> 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
> is FermatPRP.
More information about the gmp-discuss