Invert the meaning of the Miller-Rabin test; passes_test meant 'is not

a witness'. Instead call it 'is_witness', returning true if a is a
witness for n's compositness, or otherwise false.

Also, the previous version would not check that the final value of y
was n-1; if it isn't, then n is not prime. This would mean the false
negative rate was higher than it should have been, though I'm not sure
by how much exactly.

1 files changed, 17 insertions, 9 deletions

diff --git a/src/math/numbertheory/numthry.cpp b/src/math/numbertheory/numthry.cpp
index 8018c1d2d..16fa8ca0c 100644
--- a/src/math/numbertheory/numthry.cpp
+++ b/src/math/numbertheory/numthry.cpp
@@ -1,6 +1,6 @@
 /*
 * Number Theory Functions
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2011 Jack Lloyd
 *
 * Distributed under the terms of the Botan license
 */
@@ -10,6 +10,8 @@
 #include <botan/internal/bit_ops.h>
 #include <algorithm>
 
+#include <stdio.h>
+
 namespace Botan {
 
 namespace {
@@ -20,7 +22,7 @@ namespace {
 class MillerRabin_Test
    {
    public:
-      bool passes_test(const BigInt& nonce);
+      bool is_witness(const BigInt& nonce);
       MillerRabin_Test(const BigInt& num);
    private:
       BigInt n, r, n_minus_1;
@@ -30,26 +32,32 @@ class MillerRabin_Test
    };
 
 /*
-* Miller-Rabin Test
+* Miller-Rabin Test, as described in Handbook of Applied Cryptography
+* section 4.24
 */
-bool MillerRabin_Test::passes_test(const BigInt& a)
+bool MillerRabin_Test::is_witness(const BigInt& a)
    {
    if(a < 2 || a >= n_minus_1)
       throw Invalid_Argument("Bad size for nonce in Miller-Rabin test");
 
    BigInt y = pow_mod(a);
    if(y == 1 || y == n_minus_1)
-      return true;
+      return false;
 
    for(size_t i = 1; i != s; ++i)
       {
       y = reducer.square(y);
 
-      if(y == 1)
-         return false;
-      if(y == n_minus_1)
+      if(y == 1) // found a non-trivial square root
          return true;
+
+      if(y == n_minus_1) // -1, trivial square root, so give up
+         return false;
       }
+
+   if(y != n_minus_1) // fails Fermat test
+      return true;
+
    return false;
    }
 
@@ -297,7 +305,7 @@ bool primality_test(const BigInt& n,
       while(nonce < 2 || nonce >= (n-1))
          nonce.randomize(rng, NONCE_BITS);
 
-      if(!mr.passes_test(nonce))
+      if(mr.is_witness(nonce))
          return false;
       }
    return true;