diff options
author | lloyd <[email protected]> | 2008-07-05 17:01:16 +0000 |
---|---|---|
committer | lloyd <[email protected]> | 2008-07-05 17:01:16 +0000 |
commit | 7cc2151c3944f23bd43280610b15a0cbe1b52f0a (patch) | |
tree | 261e9aa9897d946d346b9fa09eb861c1362010aa | |
parent | a297e294a01fca7e5abc71e05715059711a697e5 (diff) |
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.
-rw-r--r-- | src/make_prm.cpp | 11 |
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]; |