FermatPRP vs. M-R
Paul Leyland
paul at leyland.vispa.com
Wed Mar 16 15:27:40 CET 2011
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
More information about the gmp-discuss
mailing list