From 7cc2151c3944f23bd43280610b15a0cbe1b52f0a Mon Sep 17 00:00:00 2001 From: lloyd Date: Sat, 5 Jul 2008 17:01:16 +0000 Subject: 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. --- src/make_prm.cpp | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-) (limited to 'src') 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]; -- cgit v1.2.3