Botan  2.11.0
Crypto and TLS for C++11
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 */
94  const Modular_Reducer& mod_n,
95  RandomNumberGenerator& rng,
96  size_t t);
97 
98 }
99 
100 #endif
bool is_lucas_probable_prime(const BigInt &C, const Modular_Reducer &mod_C)
Definition: primality.cpp:17
bool RandomNumberGenerator & rng
Definition: numthry.h:176
BigInt size_t n
Definition: bigint.h:1096
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
Definition: primality.cpp:168
botan_rng_t size_t n_bits
Definition: ffi.h:949
#define BOTAN_TEST_API
Definition: compiler.h:45
bool is_bailie_psw_probable_prime(const BigInt &n, const Modular_Reducer &mod_n)
Definition: primality.cpp:95
bool RandomNumberGenerator size_t prob
Definition: numthry.h:177
size_t const BigInt & a
Definition: numthry.h:111
Definition: alg_id.cpp:13
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
bool is_miller_rabin_probable_prime(const BigInt &n, const Modular_Reducer &mod_n, RandomNumberGenerator &rng, size_t test_iterations)
Definition: primality.cpp:146
class BOTAN_PUBLIC_API(2, 11) Argon2 final class BOTAN_PUBLIC_API(2, 11) Argon2_Family final void size_t const char size_t const uint8_t size_t const uint8_t size_t const uint8_t size_t uint8_t size_t size_t size_t t
Definition: argon2.h:87