Botan 3.14.1
Crypto and TLS for C&
primality.h
Go to the documentation of this file.
1/*
2* (C) 2018 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#ifndef BOTAN_PRIMALITY_TEST_H_
8#define BOTAN_PRIMALITY_TEST_H_
9
10#include <botan/types.h>
11#include <vector>
12
13namespace Botan {
14
15class BigInt;
18
19/**
20* Compute the residues of n modulo the first num_primes small odd primes
21*
22* Returns a vector r of length num_primes where r[i] == n % PRIMES[i]
23*
24* This is constant time with respect to the value of n; the primes are
25* public, and num_primes and the word length of n are leaked.
26*
27* @param n a non-negative integer
28* @param num_primes number of primes to reduce by, at most PRIME_TABLE_SIZE
29*/
30std::vector<word> BOTAN_TEST_API mod_small_primes(const BigInt& n, size_t num_primes);
31
32/**
33* Compute the residues of x modulo the first num_primes small odd primes
34*
35* Returns a vector r of length num_primes where r[i] == x % PRIMES[i]
36*
37* This is constant time with respect to the value of x
38*
39* @param x a 64-bit integer
40* @param num_primes number of primes to reduce by, at most PRIME_TABLE_SIZE
41*/
42std::vector<word> BOTAN_TEST_API mod_small_primes(uint64_t x, size_t num_primes);
43
44/**
45* Perform Lucas primality test
46* @see FIPS 186-4 C.3.3
47*
48* @warning it is possible to construct composite integers which pass
49* this test alone.
50*
51* @param n the positive integer to test
52* @param monty_n pre-created Montgomery parameters for n
53* @return true if n seems probably prime, false if n is composite
54*/
56
57/**
58* Perform Lucas primality test, taking variable time depending on n
59* @see FIPS 186-4 C.3.3
60*
61* @warning only use this if n is public
62*
63* @param n the positive integer to test
64* @param monty_n pre-created Montgomery parameters for n
65* @return true if n seems probably prime, false if n is composite
66*/
68
69/**
70* Perform Bailie-PSW primality test
71*
72* This is a combination of Miller-Rabin with base 2 and a Lucas test. No known
73* composite integer passes both tests, though it is conjectured that infinitely
74* many composite counterexamples exist.
75*
76* @param n the positive integer to test
77* @param monty_n pre-created Montgomery parameters for n
78* @return true if n seems probably prime, false if n is composite
79*/
81
82/**
83* Perform Bailie-PSW primality test, taking variable time depending on n
84*
85* @warning only use this if n is public
86*
87* @param n the positive integer to test
88* @param monty_n pre-created Montgomery parameters for n
89* @return true if n seems probably prime, false if n is composite
90*/
92
93/**
94* Perform Bailie-PSW primality test
95*
96* This variant creates the Montgomery parameters internally, and accepts any
97* non-negative integer (returning false for even or tiny values).
98*
99* @param n the positive integer to test
100* @return true if n seems probably prime, false if n is composite
101*/
103
104/**
105* Perform Bailie-PSW primality test, taking variable time depending on n
106*
107* This variant creates the Montgomery parameters internally, and accepts any
108* non-negative integer (returning false for even or tiny values).
109*
110* @warning only use this if n is public
111*
112* @param n the positive integer to test
113* @return true if n seems probably prime, false if n is composite
114*/
116
117/**
118* Return required number of Miller-Rabin tests in order to
119* reach the specified probability of error.
120*
121* @param n_bits the bit-length of the integer being tested
122* @param prob chance of false positive is bounded by 1/2**prob
123* @param random is set if (and only if) the integer was randomly generated by us
124* and thus cannot have been maliciously constructed.
125*/
126size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random);
127
128/**
129* Perform t iterations of a Miller-Rabin primality test with random bases
130*
131* @param n the positive integer to test
132* @param monty_n pre-created Montgomery parameters for n
133* @param rng a random number generator
134* @param t number of tests to perform
135*
136* @return result of primality test
137*/
139 const Montgomery_Params& monty_n,
141 size_t t);
142
143/**
144* Perform t iterations of a Miller-Rabin primality test with random bases,
145* taking variable time depending on n
146*
147* @warning only use this if n is public
148*
149* @param n the positive integer to test
150* @param monty_n pre-created Montgomery parameters for n
151* @param rng a random number generator
152* @param t number of tests to perform
153*
154* @return result of primality test
155*/
157 const Montgomery_Params& monty_n,
159 size_t t);
160
161/**
162* Perform t iterations of a Miller-Rabin primality test with random bases,
163* followed by a Lucas test.
164*
165* If a thread pool is available and the work is large enough, the tests
166* run in parallel, after a single Miller-Rabin test in the calling thread
167* has rejected most composites.
168*
169* @param n the positive integer to test
170* @param monty_n pre-created Montgomery parameters for n
171* @param rng a random number generator
172* @param t number of Miller-Rabin tests to perform
173*
174* @return result of primality test
175*/
177 const Montgomery_Params& monty_n,
179 size_t t);
180
181/**
182* Perform t iterations of a Miller-Rabin primality test with random bases,
183* followed by a Lucas test, taking variable time depending on n
184*
185* @warning only use this if n is public
186*
187* @param n the positive integer to test
188* @param monty_n pre-created Montgomery parameters for n
189* @param rng a random number generator
190* @param t number of Miller-Rabin tests to perform
191*
192* @return result of primality test
193*/
195 const Montgomery_Params& monty_n,
197 size_t t);
198
199/**
200* Check for primality, taking variable time depending on n
201*
202* This performs the same tests as is_prime, but uses variable time algorithms
203* throughout and so is faster.
204*
205* @warning only use this if n is public
206*
207* @param n a positive integer to test for primality
208* @param rng a random number generator
209* @param prob chance of false positive is bounded by 1/2**prob
210* @param is_random true if n was randomly chosen by us
211* @return true if all primality tests passed, otherwise false
212*/
213bool BOTAN_TEST_API is_prime_vartime(const BigInt& n, RandomNumberGenerator& rng, size_t prob, bool is_random);
214
215/**
216* Generate DSA parameters using the FIPS 186 kosherizer
217* @param rng a random number generator
218* @param p_out where the prime p will be stored
219* @param q_out where the prime q will be stored
220* @param pbits how long p will be in bits
221* @param qbits how long q will be in bits
222* @return random seed used to generate this parameter set
223*/
224std::vector<uint8_t> generate_dsa_primes(
225 RandomNumberGenerator& rng, BigInt& p_out, BigInt& q_out, size_t pbits, size_t qbits);
226
227/**
228* Generate DSA parameters using the FIPS 186 kosherizer
229* @param rng a random number generator
230* @param p_out where the prime p will be stored
231* @param q_out where the prime q will be stored
232* @param pbits how long p will be in bits
233* @param qbits how long q will be in bits
234* @param seed the seed used to generate the parameters
235* @param offset optional offset from seed to start searching at
236* @return true if seed generated a valid DSA parameter set, otherwise
237 false. p_out and q_out are only valid if true was returned.
238*/
240 BigInt& p_out,
241 BigInt& q_out,
242 size_t pbits,
243 size_t qbits,
244 const std::vector<uint8_t>& seed,
245 size_t offset = 0);
246
247} // namespace Botan
248
249#endif
#define BOTAN_TEST_API
Definition api.h:41
bool is_prime_vartime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition numthry.cpp:453
bool is_miller_rabin_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n, RandomNumberGenerator &rng, size_t test_iterations)
bool is_bailie_psw_probable_prime(const BigInt &n, const Montgomery_Params &monty_n)
std::vector< word > BOTAN_TEST_API mod_small_primes(const BigInt &n, size_t num_primes)
Definition primes.cpp:493
bool is_bailie_psw_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n)
bool generate_dsa_primes(RandomNumberGenerator &rng, BigInt &p, BigInt &q, size_t pbits, size_t qbits, const std::vector< uint8_t > &seed_c, size_t offset)
Definition dsa_gen.cpp:54
bool is_lucas_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n)
bool is_miller_rabin_lucas_probable_prime(const BigInt &n, const Montgomery_Params &monty_n, RandomNumberGenerator &rng, size_t test_iterations)
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
bool is_miller_rabin_probable_prime(const BigInt &n, const Montgomery_Params &monty_n, RandomNumberGenerator &rng, size_t test_iterations)
bool is_lucas_probable_prime(const BigInt &n, const Montgomery_Params &monty_n)
bool is_miller_rabin_lucas_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n, RandomNumberGenerator &rng, size_t test_iterations)