Add prime and dl_group command line tools.

Some cleanups in random_prime. Increase probability in prime tests from
1/2**64 to 1/2**128. Also break out of the sieve loop early if it has
failed.

1 files changed, 42 insertions, 14 deletions

diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp
index 1333fdf04..3d82adf06 100644
--- a/src/lib/math/numbertheory/make_prm.cpp
+++ b/src/lib/math/numbertheory/make_prm.cpp
@@ -18,22 +18,37 @@ BigInt random_prime(RandomNumberGenerator& rng,
                     size_t bits, const BigInt& coprime,
                     size_t equiv, size_t modulo)
    {
+   if(coprime <= 0)
+      {
+      throw Invalid_Argument("random_prime: coprime must be > 0");
+      }
+   if(modulo % 2 == 1 || modulo == 0)
+      {
+      throw Invalid_Argument("random_prime: Invalid modulo value");
+      }
+   if(equiv >= modulo || equiv % 2 == 0)
+      {
+      throw Invalid_Argument("random_prime: equiv must be < modulo, and odd");
+      }
+
+   // Handle small values:
    if(bits <= 1)
+      {
       throw Invalid_Argument("random_prime: Can't make a prime of " +
                              std::to_string(bits) + " bits");
+      }
    else if(bits == 2)
+      {
       return ((rng.next_byte() % 2) ? 2 : 3);
+      }
    else if(bits == 3)
+      {
       return ((rng.next_byte() % 2) ? 5 : 7);
+      }
    else if(bits == 4)
+      {
       return ((rng.next_byte() % 2) ? 11 : 13);
-
-   if(coprime <= 0)
-      throw Invalid_Argument("random_prime: coprime must be > 0");
-   if(modulo % 2 == 1 || modulo == 0)
-      throw Invalid_Argument("random_prime: Invalid modulo value");
-   if(equiv >= modulo || equiv % 2 == 0)
-      throw Invalid_Argument("random_prime: equiv must be < modulo, and odd");
+      }
 
    while(true)
       {
@@ -56,27 +71,39 @@ BigInt random_prime(RandomNumberGenerator& rng,
       size_t counter = 0;
       while(true)
          {
-         if(counter == 4096 || p.bits() > bits)
-            break;
-
-         bool passes_sieve = true;
          ++counter;
+
+         if(counter >= 4096)
+            {
+            break; // don't try forever, choose a new starting point
+            }
+
          p += modulo;
 
          if(p.bits() > bits)
             break;
 
+         bool passes_sieve = true;
          for(size_t j = 0; j != sieve.size(); ++j)
             {
             sieve[j] = (sieve[j] + modulo) % PRIMES[j];
             if(sieve[j] == 0)
+               {
                passes_sieve = false;
+               break;
+               }
             }
 
-         if(!passes_sieve || gcd(p - 1, coprime) != 1)
+         if(!passes_sieve)
+            continue;
+
+         if(gcd(p - 1, coprime) != 1)
             continue;
-         if(is_prime(p, rng, 64, true))
+
+         if(is_prime(p, rng, 128, true))
+            {
             return p;
+            }
          }
       }
    }
@@ -93,7 +120,8 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
    BigInt p;
    do
       p = (random_prime(rng, bits - 1) << 1) + 1;
-   while(!is_prime(p, rng, 64, true));
+   while(!is_prime(p, rng, 128, true));
+
    return p;
    }