Botan  1.10.9
numthry.h
Go to the documentation of this file.
1 /*
2 * Number Theory Functions
3 * (C) 1999-2007 Jack Lloyd
4 *
5 * Distributed under the terms of the Botan license
6 */
7 
8 #ifndef BOTAN_NUMBER_THEORY_H__
9 #define BOTAN_NUMBER_THEORY_H__
10 
11 #include <botan/bigint.h>
12 #include <botan/pow_mod.h>
13 #include <botan/rng.h>
14 
15 namespace Botan {
16 
17 /**
18 * Fused multiply-add
19 * @param a an integer
20 * @param b an integer
21 * @param c an integer
22 * @return (a*b)+c
23 */
24 BigInt BOTAN_DLL mul_add(const BigInt& a,
25  const BigInt& b,
26  const BigInt& c);
27 
28 /**
29 * Fused subtract-multiply
30 * @param a an integer
31 * @param b an integer
32 * @param c an integer
33 * @return (a-b)*c
34 */
35 BigInt BOTAN_DLL sub_mul(const BigInt& a,
36  const BigInt& b,
37  const BigInt& c);
38 
39 /**
40 * Return the absolute value
41 * @param n an integer
42 * @return absolute value of n
43 */
44 inline BigInt abs(const BigInt& n) { return n.abs(); }
45 
46 /**
47 * Compute the greatest common divisor
48 * @param x a positive integer
49 * @param y a positive integer
50 * @return gcd(x,y)
51 */
52 BigInt BOTAN_DLL gcd(const BigInt& x, const BigInt& y);
53 
54 /**
55 * Least common multiple
56 * @param x a positive integer
57 * @param y a positive integer
58 * @return z, smallest integer such that z % x == 0 and z % y == 0
59 */
60 BigInt BOTAN_DLL lcm(const BigInt& x, const BigInt& y);
61 
62 /**
63 * @param x an integer
64 * @return (x*x)
65 */
66 BigInt BOTAN_DLL square(const BigInt& x);
67 
68 /**
69 * Modular inversion
70 * @param x a positive integer
71 * @param modulus a positive integer
72 * @return y st (x*y) % modulus == 1
73 */
74 BigInt BOTAN_DLL inverse_mod(const BigInt& x,
75  const BigInt& modulus);
76 
77 /**
78 * Compute the Jacobi symbol. If n is prime, this is equivalent
79 * to the Legendre symbol.
80 * @see http://mathworld.wolfram.com/JacobiSymbol.html
81 *
82 * @param a is a non-negative integer
83 * @param n is an odd integer > 1
84 * @return (n / m)
85 */
86 s32bit BOTAN_DLL jacobi(const BigInt& a,
87  const BigInt& n);
88 
89 /**
90 * Modular exponentation
91 * @param b an integer base
92 * @param x a positive exponent
93 * @param m a positive modulus
94 * @return (b^x) % m
95 */
96 BigInt BOTAN_DLL power_mod(const BigInt& b,
97  const BigInt& x,
98  const BigInt& m);
99 
100 /**
101 * Compute the square root of x modulo a prime using the
102 * Shanks-Tonnelli algorithm
103 *
104 * @param x the input
105 * @param p the prime
106 * @return y such that (y*y)%p == x, or -1 if no such integer
107 */
108 BigInt BOTAN_DLL ressol(const BigInt& x, const BigInt& p);
109 
110 /**
111 * @param x an integer
112 * @return count of the zero bits in x, or, equivalently, the largest
113 * value of n such that 2^n divides x evently
114 */
115 size_t BOTAN_DLL low_zero_bits(const BigInt& x);
116 
117 /**
118 * Primality Testing
119 * @param n a positive integer to test for primality
120 * @param rng a random number generator
121 * @param level how hard to test
122 * @return true if all primality tests passed, otherwise false
123 */
124 bool BOTAN_DLL primality_test(const BigInt& n,
125  RandomNumberGenerator& rng,
126  size_t level = 1);
127 
128 /**
129 * Quickly check for primality
130 * @param n a positive integer to test for primality
131 * @param rng a random number generator
132 * @return true if all primality tests passed, otherwise false
133 */
135  { return primality_test(n, rng, 0); }
136 
137 /**
138 * Check for primality
139 * @param n a positive integer to test for primality
140 * @param rng a random number generator
141 * @return true if all primality tests passed, otherwise false
142 */
144  { return primality_test(n, rng, 1); }
145 
146 /**
147 * Verify primality - this function is slow but useful if you want to
148 * ensure that a possibly malicious entity did not provide you with
149 * something that 'looks like' a prime
150 * @param n a positive integer to test for primality
151 * @param rng a random number generator
152 * @return true if all primality tests passed, otherwise false
153 */
155  { return primality_test(n, rng, 2); }
156 
157 /**
158 * Randomly generate a prime
159 * @param rng a random number generator
160 * @param bits how large the resulting prime should be in bits
161 * @param coprime a positive integer the result should be coprime to
162 * @param equiv a non-negative number that the result should be
163  equivalent to modulo equiv_mod
164 * @param equiv_mod the modulus equiv should be checked against
165 * @return random prime with the specified criteria
166 */
167 BigInt BOTAN_DLL random_prime(RandomNumberGenerator& rng,
168  size_t bits, const BigInt& coprime = 1,
169  size_t equiv = 1, size_t equiv_mod = 2);
170 
171 /**
172 * Return a 'safe' prime, of the form p=2*q+1 with q prime
173 * @param rng a random number generator
174 * @param bits is how long the resulting prime should be
175 * @return prime randomly chosen from safe primes of length bits
176 */
177 BigInt BOTAN_DLL random_safe_prime(RandomNumberGenerator& rng,
178  size_t bits);
179 
180 class Algorithm_Factory;
181 
182 /**
183 * Generate DSA parameters using the FIPS 186 kosherizer
184 * @param rng a random number generator
185 * @param af an algorithm factory
186 * @param p_out where the prime p will be stored
187 * @param q_out where the prime q will be stored
188 * @param pbits how long p will be in bits
189 * @param qbits how long q will be in bits
190 * @return random seed used to generate this parameter set
191 */
192 SecureVector<byte> BOTAN_DLL
193 generate_dsa_primes(RandomNumberGenerator& rng,
194  Algorithm_Factory& af,
195  BigInt& p_out, BigInt& q_out,
196  size_t pbits, size_t qbits);
197 
198 /**
199 * Generate DSA parameters using the FIPS 186 kosherizer
200 * @param rng a random number generator
201 * @param af an algorithm factory
202 * @param p_out where the prime p will be stored
203 * @param q_out where the prime q will be stored
204 * @param pbits how long p will be in bits
205 * @param qbits how long q will be in bits
206 * @param seed the seed used to generate the parameters
207 * @return true if seed generated a valid DSA parameter set, otherwise
208  false. p_out and q_out are only valid if true was returned.
209 */
210 bool BOTAN_DLL
211 generate_dsa_primes(RandomNumberGenerator& rng,
212  Algorithm_Factory& af,
213  BigInt& p_out, BigInt& q_out,
214  size_t pbits, size_t qbits,
215  const MemoryRegion<byte>& seed);
216 
217 /**
218 * The size of the PRIMES[] array
219 */
220 const size_t PRIME_TABLE_SIZE = 6541;
221 
222 /**
223 * A const array of all primes less than 65535
224 */
225 extern const u16bit BOTAN_DLL PRIMES[];
226 
227 }
228 
229 #endif
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:220
BigInt n
Definition: numthry.cpp:26
BigInt gcd(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:167
bool quick_check_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:134
BigInt abs() const
Definition: bigint.cpp:330
BigInt BOTAN_DLL ressol(const BigInt &x, const BigInt &p)
Definition: ressol.cpp:17
signed int s32bit
Definition: types.h:37
bool primality_test(const BigInt &n, RandomNumberGenerator &rng, size_t level)
Definition: numthry.cpp:262
RandomNumberGenerator * rng
Definition: global_rng.cpp:165
BigInt abs(const BigInt &n)
Definition: numthry.h:44
bool verify_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:154
unsigned short u16bit
Definition: types.h:27
s32bit jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:87
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:141
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:202
BigInt sub_mul(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:60
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:18
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:251
const u16bit BOTAN_DLL PRIMES[]
Definition: primes.cpp:12
bool generate_dsa_primes(RandomNumberGenerator &rng, Algorithm_Factory &af, BigInt &p, BigInt &q, size_t pbits, size_t qbits, const MemoryRegion< byte > &seed_c)
Definition: dsa_gen.cpp:41
BigInt lcm(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:194
BigInt mul_add(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:33
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo)
Definition: make_prm.cpp:17
bool check_prime(const BigInt &n, RandomNumberGenerator &rng)
Definition: numthry.h:143