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/numthry.h | |
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/numthry.h')
-rw-r--r-- | botan/src/math/numbertheory/numthry.h | 120 |
1 files changed, 120 insertions, 0 deletions
diff --git a/botan/src/math/numbertheory/numthry.h b/botan/src/math/numbertheory/numthry.h new file mode 100644 index 0000000..e4c0437 --- /dev/null +++ b/botan/src/math/numbertheory/numthry.h @@ -0,0 +1,120 @@ +/* +* Number Theory Functions +* (C) 1999-2007 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_NUMBER_THEORY_H__ +#define BOTAN_NUMBER_THEORY_H__ + +#include <botan/bigint.h> +#include <botan/reducer.h> +#include <botan/pow_mod.h> +#include <botan/rng.h> + +namespace Botan { + +/* +* Fused Arithmetic Operations +*/ +BigInt BOTAN_DLL mul_add(const BigInt&, const BigInt&, const BigInt&); +BigInt BOTAN_DLL sub_mul(const BigInt&, const BigInt&, const BigInt&); + +/* +* Number Theory Functions +*/ +inline BigInt abs(const BigInt& n) { return n.abs(); } + +void BOTAN_DLL divide(const BigInt&, const BigInt&, BigInt&, BigInt&); + +BigInt BOTAN_DLL gcd(const BigInt&, const BigInt&); +BigInt BOTAN_DLL lcm(const BigInt&, const BigInt&); + +BigInt BOTAN_DLL square(const BigInt&); +BigInt BOTAN_DLL inverse_mod(const BigInt&, const BigInt&); +s32bit BOTAN_DLL jacobi(const BigInt&, const BigInt&); + +BigInt BOTAN_DLL power_mod(const BigInt&, const BigInt&, const BigInt&); + +/* +* Compute the square root of x modulo a prime +* using the Shanks-Tonnelli algorithm +*/ +BigInt ressol(const BigInt& x, const BigInt& p); + +/* +* Utility Functions +*/ +u32bit BOTAN_DLL low_zero_bits(const BigInt&); + +/* +* Primality Testing +*/ +bool BOTAN_DLL check_prime(const BigInt&, RandomNumberGenerator&); +bool BOTAN_DLL is_prime(const BigInt&, RandomNumberGenerator&); +bool BOTAN_DLL verify_prime(const BigInt&, RandomNumberGenerator&); + +s32bit BOTAN_DLL simple_primality_tests(const BigInt&); + +bool BOTAN_DLL passes_mr_tests(RandomNumberGenerator&, + const BigInt&, u32bit = 1); + +bool BOTAN_DLL run_primality_tests(RandomNumberGenerator&, + const BigInt&, u32bit = 1); + +/* +* Random Number Generation +*/ +BigInt BOTAN_DLL random_prime(RandomNumberGenerator&, + u32bit bits, const BigInt& coprime = 1, + u32bit equiv = 1, u32bit equiv_mod = 2); + +BigInt BOTAN_DLL random_safe_prime(RandomNumberGenerator&, + u32bit); + +/* +* DSA Parameter Generation +*/ +class Algorithm_Factory; + +SecureVector<byte> BOTAN_DLL +generate_dsa_primes(RandomNumberGenerator& rng, + Algorithm_Factory& af, + BigInt& p, BigInt& q, + u32bit pbits, u32bit qbits); + +bool BOTAN_DLL +generate_dsa_primes(RandomNumberGenerator& rng, + Algorithm_Factory& af, + BigInt& p_out, BigInt& q_out, + u32bit p_bits, u32bit q_bits, + const MemoryRegion<byte>& seed); + +/* +* Prime Numbers +*/ +const u32bit PRIME_TABLE_SIZE = 6541; +const u32bit PRIME_PRODUCTS_TABLE_SIZE = 256; + +extern const u16bit BOTAN_DLL PRIMES[]; +extern const u64bit PRIME_PRODUCTS[]; + +/* +* Miller-Rabin Primality Tester +*/ +class BOTAN_DLL MillerRabin_Test + { + public: + bool passes_test(const BigInt&); + MillerRabin_Test(const BigInt&); + private: + BigInt n, r, n_minus_1; + u32bit s; + Fixed_Exponent_Power_Mod pow_mod; + Modular_Reducer reducer; + }; + +} + +#endif |