Any fixed MR iterations is probably wrong for somebody. Allow the user

to specify a probability as well as if n was randomly chosen or not.
If the input is random use a better bounds to reduce the number of
needed tests.

4 files changed, 49 insertions, 7 deletions

diff --git a/src/lib/math/numbertheory/dsa_gen.cpp b/src/lib/math/numbertheory/dsa_gen.cpp
index f14481f9c..796fb6ec2 100644
--- a/src/lib/math/numbertheory/dsa_gen.cpp
+++ b/src/lib/math/numbertheory/dsa_gen.cpp
@@ -82,7 +82,7 @@ bool generate_dsa_primes(RandomNumberGenerator& rng,
    q.set_bit(qbits-1);
    q.set_bit(0);
 
-   if(!check_prime(q, rng))
+   if(!is_prime(q, rng))
       return false;
 
    const size_t n = (pbits-1) / (HASH_SIZE * 8),
@@ -106,7 +106,7 @@ bool generate_dsa_primes(RandomNumberGenerator& rng,
 
       p = X - (X % (2*q) - 1);
 
-      if(p.bits() == pbits && check_prime(p, rng))
+      if(p.bits() == pbits && is_prime(p, rng))
          return true;
       }
    return false;
diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp
index dc94420ab..2c8cd086d 100644
--- a/src/lib/math/numbertheory/make_prm.cpp
+++ b/src/lib/math/numbertheory/make_prm.cpp
@@ -75,7 +75,7 @@ BigInt random_prime(RandomNumberGenerator& rng,
 
          if(!passes_sieve || gcd(p - 1, coprime) != 1)
             continue;
-         if(check_prime(p, rng))
+         if(is_prime(p, rng, 64, true))
             return p;
          }
       }
@@ -93,7 +93,7 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
    BigInt p;
    do
       p = (random_prime(rng, bits - 1) << 1) + 1;
-   while(!check_prime(p, rng));
+   while(!is_prime(p, rng, 64, true));
    return p;
    }
 
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 998b0b53b..ce25b5047 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -253,12 +253,39 @@ bool mr_witness(BigInt&& y,
    return true; // fails Fermat test
    }
 
+size_t mr_test_iterations(size_t n_bits, size_t prob, bool random)
+   {
+   const size_t base = (prob + 2) / 2; // worst case 4^-t error rate
+
+   /*
+   * For randomly chosen numbers we can use the estimates from
+   * http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf‎
+   *
+   * These values are derived from the inequality for p(k,t) given on
+   * the second page.
+   */
+   if(random && prob <= 80)
+      {
+      if(n_bits >= 1536)
+         return 2; // < 2^-89
+      if(n_bits >= 1024)
+         return 4; // < 2^-89
+      if(n_bits >= 512)
+         return 5; // < 2^-80
+      if(n_bits >= 256)
+         return 11; // < 2^-80
+      }
+
+   return base;
+   }
+
 }
 
 /*
 * Test for primaility using Miller-Rabin
 */
-bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
+bool is_prime(const BigInt& n, RandomNumberGenerator& rng,
+              size_t prob, bool is_random)
    {
    if(n == 2)
       return true;
@@ -273,7 +300,7 @@ bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
       return std::binary_search(PRIMES, PRIMES + PRIME_TABLE_SIZE, num);
       }
 
-   const size_t test_iterations = 20;
+   const size_t test_iterations = mr_test_iterations(n.bits(), prob, is_random);
 
    const BigInt n_minus_1 = n - 1;
    const size_t s = low_zero_bits(n_minus_1);
diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h
index cb73356b2..5499ff76f 100644
--- a/src/lib/math/numbertheory/numthry.h
+++ b/src/lib/math/numbertheory/numthry.h
@@ -126,9 +126,24 @@ size_t BOTAN_DLL low_zero_bits(const BigInt& x);
 * Check for primality
 * @param n a positive integer to test for primality
 * @param rng a random number generator
+* @param prob chance of false positive is bounded by 1/2**prob
+* @param is_random true if n was randomly chosen by us
 * @return true if all primality tests passed, otherwise false
 */
-bool BOTAN_DLL check_prime(const BigInt& n, RandomNumberGenerator& rng);
+bool BOTAN_DLL is_prime(const BigInt& n,
+                        RandomNumberGenerator& rng,
+                        size_t prob = 56,
+                        bool is_random = false);
+
+inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
+   { return is_prime(n, rng, 32); }
+
+inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
+   { return is_prime(n, rng, 56); }
+
+inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
+   { return is_prime(n, rng, 80); }
+
 
 /**
 * Randomly generate a prime