Botan  1.11.15
src/lib/math/numbertheory/numthry.h
Go to the documentation of this file.
00001 /*
00002 * Number Theory Functions
00003 * (C) 1999-2007 Jack Lloyd
00004 *
00005 * Botan is released under the Simplified BSD License (see license.txt)
00006 */
00007 
00008 #ifndef BOTAN_NUMBER_THEORY_H__
00009 #define BOTAN_NUMBER_THEORY_H__
00010 
00011 #include <botan/bigint.h>
00012 #include <botan/pow_mod.h>
00013 #include <botan/rng.h>
00014 
00015 namespace Botan {
00016 
00017 /**
00018 * Fused multiply-add
00019 * @param a an integer
00020 * @param b an integer
00021 * @param c an integer
00022 * @return (a*b)+c
00023 */
00024 BigInt BOTAN_DLL mul_add(const BigInt& a,
00025                          const BigInt& b,
00026                          const BigInt& c);
00027 
00028 /**
00029 * Fused subtract-multiply
00030 * @param a an integer
00031 * @param b an integer
00032 * @param c an integer
00033 * @return (a-b)*c
00034 */
00035 BigInt BOTAN_DLL sub_mul(const BigInt& a,
00036                          const BigInt& b,
00037                          const BigInt& c);
00038 
00039 /**
00040 * Return the absolute value
00041 * @param n an integer
00042 * @return absolute value of n
00043 */
00044 inline BigInt abs(const BigInt& n) { return n.abs(); }
00045 
00046 /**
00047 * Compute the greatest common divisor
00048 * @param x a positive integer
00049 * @param y a positive integer
00050 * @return gcd(x,y)
00051 */
00052 BigInt BOTAN_DLL gcd(const BigInt& x, const BigInt& y);
00053 
00054 /**
00055 * Least common multiple
00056 * @param x a positive integer
00057 * @param y a positive integer
00058 * @return z, smallest integer such that z % x == 0 and z % y == 0
00059 */
00060 BigInt BOTAN_DLL lcm(const BigInt& x, const BigInt& y);
00061 
00062 /**
00063 * @param x an integer
00064 * @return (x*x)
00065 */
00066 BigInt BOTAN_DLL square(const BigInt& x);
00067 
00068 /**
00069 * Modular inversion
00070 * @param x a positive integer
00071 * @param modulus a positive integer
00072 * @return y st (x*y) % modulus == 1
00073 */
00074 BigInt BOTAN_DLL inverse_mod(const BigInt& x,
00075                              const BigInt& modulus);
00076 
00077 /**
00078 * Compute the Jacobi symbol. If n is prime, this is equivalent
00079 * to the Legendre symbol.
00080 * @see http://mathworld.wolfram.com/JacobiSymbol.html
00081 *
00082 * @param a is a non-negative integer
00083 * @param n is an odd integer > 1
00084 * @return (n / m)
00085 */
00086 s32bit BOTAN_DLL jacobi(const BigInt& a,
00087                         const BigInt& n);
00088 
00089 /**
00090 * Modular exponentation
00091 * @param b an integer base
00092 * @param x a positive exponent
00093 * @param m a positive modulus
00094 * @return (b^x) % m
00095 */
00096 BigInt BOTAN_DLL power_mod(const BigInt& b,
00097                            const BigInt& x,
00098                            const BigInt& m);
00099 
00100 /**
00101 * Compute the square root of x modulo a prime using the
00102 * Shanks-Tonnelli algorithm
00103 *
00104 * @param x the input
00105 * @param p the prime
00106 * @return y such that (y*y)%p == x, or -1 if no such integer
00107 */
00108 BigInt BOTAN_DLL ressol(const BigInt& x, const BigInt& p);
00109 
00110 /*
00111 * Compute -input^-1 mod 2^MP_WORD_BITS. Returns zero if input
00112 * is even. If input is odd, input and 2^n are relatively prime
00113 * and an inverse exists.
00114 */
00115 word BOTAN_DLL monty_inverse(word input);
00116 
00117 /**
00118 * @param x a positive integer
00119 * @return count of the zero bits in x, or, equivalently, the largest
00120 *         value of n such that 2^n divides x evenly. Returns zero if
00121 *         n is less than or equal to zero.
00122 */
00123 size_t BOTAN_DLL low_zero_bits(const BigInt& x);
00124 
00125 /**
00126 * Check for primality
00127 * @param n a positive integer to test for primality
00128 * @param rng a random number generator
00129 * @param prob chance of false positive is bounded by 1/2**prob
00130 * @param is_random true if n was randomly chosen by us
00131 * @return true if all primality tests passed, otherwise false
00132 */
00133 bool BOTAN_DLL is_prime(const BigInt& n,
00134                         RandomNumberGenerator& rng,
00135                         size_t prob = 56,
00136                         bool is_random = false);
00137 
00138 inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
00139    { return is_prime(n, rng, 32); }
00140 
00141 inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
00142    { return is_prime(n, rng, 56); }
00143 
00144 inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
00145    { return is_prime(n, rng, 80); }
00146 
00147 
00148 /**
00149 * Randomly generate a prime
00150 * @param rng a random number generator
00151 * @param bits how large the resulting prime should be in bits
00152 * @param coprime a positive integer the result should be coprime to
00153 * @param equiv a non-negative number that the result should be
00154                equivalent to modulo equiv_mod
00155 * @param equiv_mod the modulus equiv should be checked against
00156 * @return random prime with the specified criteria
00157 */
00158 BigInt BOTAN_DLL random_prime(RandomNumberGenerator& rng,
00159                               size_t bits, const BigInt& coprime = 1,
00160                               size_t equiv = 1, size_t equiv_mod = 2);
00161 
00162 /**
00163 * Return a 'safe' prime, of the form p=2*q+1 with q prime
00164 * @param rng a random number generator
00165 * @param bits is how long the resulting prime should be
00166 * @return prime randomly chosen from safe primes of length bits
00167 */
00168 BigInt BOTAN_DLL random_safe_prime(RandomNumberGenerator& rng,
00169                                    size_t bits);
00170 
00171 /**
00172 * Generate DSA parameters using the FIPS 186 kosherizer
00173 * @param rng a random number generator
00174 * @param af an algorithm factory
00175 * @param p_out where the prime p will be stored
00176 * @param q_out where the prime q will be stored
00177 * @param pbits how long p will be in bits
00178 * @param qbits how long q will be in bits
00179 * @return random seed used to generate this parameter set
00180 */
00181 std::vector<byte> BOTAN_DLL
00182 generate_dsa_primes(RandomNumberGenerator& rng,
00183                     BigInt& p_out, BigInt& q_out,
00184                     size_t pbits, size_t qbits);
00185 
00186 /**
00187 * Generate DSA parameters using the FIPS 186 kosherizer
00188 * @param rng a random number generator
00189 * @param af an algorithm factory
00190 * @param p_out where the prime p will be stored
00191 * @param q_out where the prime q will be stored
00192 * @param pbits how long p will be in bits
00193 * @param qbits how long q will be in bits
00194 * @param seed the seed used to generate the parameters
00195 * @return true if seed generated a valid DSA parameter set, otherwise
00196           false. p_out and q_out are only valid if true was returned.
00197 */
00198 bool BOTAN_DLL
00199 generate_dsa_primes(RandomNumberGenerator& rng,
00200                     BigInt& p_out, BigInt& q_out,
00201                     size_t pbits, size_t qbits,
00202                     const std::vector<byte>& seed);
00203 
00204 /**
00205 * The size of the PRIMES[] array
00206 */
00207 const size_t PRIME_TABLE_SIZE = 6541;
00208 
00209 /**
00210 * A const array of all primes less than 65535
00211 */
00212 extern const u16bit BOTAN_DLL PRIMES[];
00213 
00214 }
00215 
00216 #endif