FermatPRP vs. M-R
paul at leyland.vispa.com
Wed Mar 16 16:02:48 CET 2011
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
> > 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.
More information about the gmp-discuss