| Science Forum Index » Cryptography Forum » Miller-Rabin and false negatives... |
|
Page 1 of 1 |
|
| Author |
Message |
| yawnmoth... |
 Posted: Sat Oct 24, 2009 4:26 am |
|
|
|
Guest
|
correct me if I'm wrong, but it seems like the only error the Miller-
Rabin primality testing algorithm is capable of generating are false
positives (flaggin a number as prime when it's really composite)?
That false negatives (flagging a number as composite when it's really
prime) are not possible? |
|
|
| Back to top |
|
|
|
| Tom St Denis... |
| Posted: Sat Oct 24, 2009 4:41 am |
|
|
|
Guest
|
On Oct 24, 10:26 am, yawnmoth <terra1... at (no spam) yahoo.com> wrote:
[quote]correct me if I'm wrong, but it seems like the only error the Miller-
Rabin primality testing algorithm is capable of generating are false
positives (flaggin a number as prime when it's really composite)?
That false negatives (flagging a number as composite when it's really
prime) are not possible?
[/quote]
Yes, because what you'd end up with is a number that isn't congruent
to 1 or -1 being squared to 1.
Tom |
|
|
| Back to top |
|
|
|
|
