[prev in list] [next in list] [prev in thread] [next in thread]
List: gmp-discuss
Subject: FermatPRP vs. M-R
From: paul () leyland ! vispa ! com (Paul Leyland)
Date: 2011-03-16 15:02:48
Message-ID: 1300287768.10846.31.camel () anubis ! home ! brnikat ! com
[Download RAW message or body]
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
your statements.
> > 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.
Paul
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic