diff options
author | Keith Isdale <keith.isdale@nokia.com> | 2010-07-26 14:56:53 +1000 |
---|---|---|
committer | Keith Isdale <keith.isdale@nokia.com> | 2010-07-26 14:56:53 +1000 |
commit | 9f034793bcfc51c2b7c1dd14db806f7258f9a9eb (patch) | |
tree | 63bd0f50ce5b77828ad8205eafd7b9412810499e /botan/src/math/numbertheory/make_prm.cpp | |
parent | 619d92cfef29e653bfdf852e83888e50cfc4348f (diff) | |
parent | 65271649dbc90f3af1184ad1b23bdb64c0c07d07 (diff) |
Merge branch 'master' of git://git-nokia.trolltech.com.au/qtsoftware/research/qtuitest
Diffstat (limited to 'botan/src/math/numbertheory/make_prm.cpp')
-rw-r--r-- | botan/src/math/numbertheory/make_prm.cpp | 97 |
1 files changed, 97 insertions, 0 deletions
diff --git a/botan/src/math/numbertheory/make_prm.cpp b/botan/src/math/numbertheory/make_prm.cpp new file mode 100644 index 0000000..b136b6d --- /dev/null +++ b/botan/src/math/numbertheory/make_prm.cpp @@ -0,0 +1,97 @@ +/* +* Prime Generation +* (C) 1999-2007 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include <botan/numthry.h> +#include <botan/parsing.h> +#include <algorithm> + +namespace Botan { + +/* +* Generate a random prime +*/ +BigInt random_prime(RandomNumberGenerator& rng, + u32bit bits, const BigInt& coprime, + u32bit equiv, u32bit modulo) + { + 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() % 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) + { + BigInt p(rng, bits); + p.set_bit(bits - 2); + p.set_bit(0); + + if(p % modulo != equiv) + p += (modulo - p % modulo) + equiv; + + const u32bit sieve_size = std::min(bits / 2, PRIME_TABLE_SIZE); + SecureVector<u32bit> sieve(sieve_size); + + for(u32bit j = 0; j != sieve.size(); ++j) + sieve[j] = p % PRIMES[j]; + + u32bit counter = 0; + while(true) + { + if(counter == 4096 || p.bits() > bits) + break; + + bool passes_sieve = true; + ++counter; + p += modulo; + + if(p.bits() > bits) + break; + + for(u32bit j = 0; j != sieve.size(); ++j) + { + sieve[j] = (sieve[j] + modulo) % PRIMES[j]; + if(sieve[j] == 0) + passes_sieve = false; + } + + if(!passes_sieve || gcd(p - 1, coprime) != 1) + continue; + if(passes_mr_tests(rng, p)) + return p; + } + } + } + +/* +* Generate a random safe prime +*/ +BigInt random_safe_prime(RandomNumberGenerator& rng, u32bit bits) + { + if(bits <= 64) + throw Invalid_Argument("random_safe_prime: Can't make a prime of " + + to_string(bits) + " bits"); + + BigInt p; + do + p = (random_prime(rng, bits - 1) << 1) + 1; + while(!is_prime(p, rng)); + return p; + } + +} |