First update the sieve, then check for a match

This allows shortcutting the checks

Use (p-1)/2 instead p/2, same result because p is odd but confusing.

1 files changed, 7 insertions, 3 deletions

diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp
index 70ef23e5a..bd0ae8e92 100644
--- a/src/lib/math/numbertheory/make_prm.cpp
+++ b/src/lib/math/numbertheory/make_prm.cpp
@@ -1,6 +1,6 @@
 /*
 * Prime Generation
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2007,2018 Jack Lloyd
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */
@@ -97,11 +97,15 @@ BigInt random_prime(RandomNumberGenerator& rng,
          if(p.bits() > bits)
             break;
 
-         bool passes_sieve = true;
+         // Now that p is updated, update the sieve
          for(size_t i = 0; i != sieve.size(); ++i)
             {
             sieve[i] = (sieve[i] + modulo) % PRIMES[i];
+            }
 
+         bool passes_sieve = true;
+         for(size_t i = 0; passes_sieve && (i != sieve.size()); ++i)
+            {
             /*
             In this case, p is a multiple of PRIMES[i]
             */
@@ -119,7 +123,7 @@ BigInt random_prime(RandomNumberGenerator& rng,
             See "Safe Prime Generation with a Combined Sieve" M. Wiener
             https://eprint.iacr.org/2003/186.pdf
             */
-            if(sieve[i] == PRIMES[i] / 2)
+            if(sieve[i] == (PRIMES[i] - 1) / 2)
                passes_sieve = false;
             }