Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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 <memory>
12
13 namespace Botan {
14
15 class BigInt;
16 class Modular_Reducer;
17 class Montgomery_Params;
18 class RandomNumberGenerator;
19
20 /**
21 * Perform Lucas primality test
22 * @see FIPS 186-4 C.3.3
23 *
24 * @warning it is possible to construct composite integers which pass
25 * this test alone.
26 *
27 * @param n the positive integer to test
28 * @param mod_n a pre-created Modular_Reducer for n
29 * @return true if n seems probably prime, false if n is composite
30 */
31 bool BOTAN_TEST_API is_lucas_probable_prime(const BigInt& n, const Modular_Reducer& mod_n);
32
33 /**
34 * Perform Bailie-PSW primality test
35 *
36 * This is a combination of Miller-Rabin with base 2 and a Lucas test. No known
37 * composite integer passes both tests, though it is conjectured that infinitely
38 * many composite counterexamples exist.
39 *
40 * @param n the positive integer to test
41 * @param mod_n a pre-created Modular_Reducer for n
42 * @return true if n seems probably prime, false if n is composite
43 */
44 bool BOTAN_TEST_API is_bailie_psw_probable_prime(const BigInt& n, const Modular_Reducer& mod_n);
45
46 /**
47 * Perform Bailie-PSW primality test
48 *
49 * This is a combination of Miller-Rabin with base 2 and a Lucas test. No known
50 * composite integer passes both tests, though it is conjectured that infinitely
51 * many composite counterexamples exist.
52 *
53 * @param n the positive integer to test
54 * @return true if n seems probably prime, false if n is composite
55 */
56 bool is_bailie_psw_probable_prime(const BigInt& n);
57
58 /**
59 * Return required number of Miller-Rabin tests in order to
60 * reach the specified probability of error.
61 *
62 * @param n_bits the bit-length of the integer being tested
63 * @param prob chance of false positive is bounded by 1/2**prob
64 * @param random is set if (and only if) the integer was randomly generated by us
65 * and thus cannot have been maliciously constructed.
66 */
67 size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random);
68
69 /**
70 * Perform a single Miller-Rabin test with specified base
71 *
72 * @param n the positive integer to test
73 * @param mod_n a pre-created Modular_Reducer for n
74 * @param monty_n Montgomery parameters for n
75 * @param a the base to check
76 * @return result of primality test
77 */
78 bool passes_miller_rabin_test(const BigInt& n,
79 const Modular_Reducer& mod_n,
80 const std::shared_ptr<Montgomery_Params>& monty_n,
81 const BigInt& a);
82
83 /**
84 * Perform t iterations of a Miller-Rabin primality test with random bases
85 *
86 * @param n the positive integer to test
87 * @param mod_n a pre-created Modular_Reducer for n
88 * @param rng a random number generator
89 * @param t number of tests to perform
90 *
91 * @return result of primality test
92 */
93 bool BOTAN_TEST_API is_miller_rabin_probable_prime(const BigInt& n,
94 const Modular_Reducer& mod_n,
95 RandomNumberGenerator& rng,
96 size_t t);
97
98 }
99
100 #endif
Botan::is_lucas_probable_prime
bool is_lucas_probable_prime(const BigInt &C, const Modular_Reducer &mod_C)
Definition: primality.cpp:17
Botan::miller_rabin_test_iterations
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
Definition: primality.cpp:168
BOTAN_TEST_API
#define BOTAN_TEST_API
Definition: compiler.h:45
Botan::is_bailie_psw_probable_prime
bool is_bailie_psw_probable_prime(const BigInt &n, const Modular_Reducer &mod_n)
Definition: primality.cpp:95
Botan
Definition: alg_id.cpp:13
Botan::passes_miller_rabin_test
bool passes_miller_rabin_test(const BigInt &n, const Modular_Reducer &mod_n, const std::shared_ptr< Montgomery_Params > &monty_n, const BigInt &a)
Definition: primality.cpp:107
Botan::is_miller_rabin_probable_prime
bool is_miller_rabin_probable_prime(const BigInt &n, const Modular_Reducer &mod_n, RandomNumberGenerator &rng, size_t test_iterations)
Definition: primality.cpp:146