Extend random_prime() to be able to generate primes of any bit size.

bits <= 1 -> error
bits == 2 -> choose 2 or 3 at random
bits == 3 -> choose 5 or 7 at random
bits == 4 -> choose 11 or 13 at random
bits >= 5 -> procedure used previously.

Tested by running random_prime() with random bit sizes <= 16 until it had
generated all <= 16 bit primes.

1 files changed, 10 insertions, 1 deletions

diff --git a/src/make_prm.cpp b/src/make_prm.cpp
index 35d1dde38..dc26a0400 100644
--- a/src/make_prm.cpp
+++ b/src/make_prm.cpp
@@ -16,9 +16,15 @@ BigInt random_prime(RandomNumberGenerator& rng,
                     u32bit bits, const BigInt& coprime,
                     u32bit equiv, u32bit modulo)
    {
-   if(bits < 48)
+   if(bits <= 1)
       throw Invalid_Argument("random_prime: Can't make a prime of " +
                              to_string(bits) + " bits");
+   else if(bits == 2)
+      return ((rng.next_byte() % 1) ? 2 : 3);
+   else if(bits == 3)
+      return ((rng.next_byte() % 1) ? 5 : 7);
+   else if(bits == 4)
+      return ((rng.next_byte() % 1) ? 11 : 13);
 
    if(coprime <= 0)
       throw Invalid_Argument("random_prime: coprime must be > 0");
@@ -52,6 +58,9 @@ BigInt random_prime(RandomNumberGenerator& rng,
          ++counter;
          p += modulo;
 
+         if(p.bits() > bits)
+            break;
+
          for(u32bit j = 0; j != sieve.size(); ++j)
             {
             sieve[j] = (sieve[j] + modulo) % PRIMES[j];