Botan 3.5.0
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 <memory>
12#include <vector>
13
14namespace Botan {
15
16class BigInt;
17class Modular_Reducer;
18class Montgomery_Params;
19class RandomNumberGenerator;
20
21/**
22* Perform Lucas primality test
23* @see FIPS 186-4 C.3.3
24*
25* @warning it is possible to construct composite integers which pass
26* this test alone.
27*
28* @param n the positive integer to test
29* @param mod_n a pre-created Modular_Reducer for n
30* @return true if n seems probably prime, false if n is composite
31*/
32bool BOTAN_TEST_API is_lucas_probable_prime(const BigInt& n, const Modular_Reducer& mod_n);
33
34/**
35* Perform Bailie-PSW primality test
36*
37* This is a combination of Miller-Rabin with base 2 and a Lucas test. No known
38* composite integer passes both tests, though it is conjectured that infinitely
39* many composite counterexamples exist.
40*
41* @param n the positive integer to test
42* @param mod_n a pre-created Modular_Reducer for n
43* @return true if n seems probably prime, false if n is composite
44*/
45bool BOTAN_TEST_API is_bailie_psw_probable_prime(const BigInt& n, const Modular_Reducer& mod_n);
46
47/**
48* Perform Bailie-PSW primality test
49*
50* This is a combination of Miller-Rabin with base 2 and a Lucas test. No known
51* composite integer passes both tests, though it is conjectured that infinitely
52* many composite counterexamples exist.
53*
54* @param n the positive integer to test
55* @return true if n seems probably prime, false if n is composite
56*/
57bool is_bailie_psw_probable_prime(const BigInt& n);
58
59/**
60* Return required number of Miller-Rabin tests in order to
61* reach the specified probability of error.
62*
63* @param n_bits the bit-length of the integer being tested
64* @param prob chance of false positive is bounded by 1/2**prob
65* @param random is set if (and only if) the integer was randomly generated by us
66* and thus cannot have been maliciously constructed.
67*/
68size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random);
69
70/**
71* Perform a single Miller-Rabin test with specified base
72*
73* @param n the positive integer to test
74* @param mod_n a pre-created Modular_Reducer for n
75* @param monty_n Montgomery parameters for n
76* @param a the base to check
77* @return result of primality test
78*/
79bool passes_miller_rabin_test(const BigInt& n,
80 const Modular_Reducer& mod_n,
81 const std::shared_ptr<Montgomery_Params>& monty_n,
82 const BigInt& a);
83
84/**
85* Perform t iterations of a Miller-Rabin primality test with random bases
86*
87* @param n the positive integer to test
88* @param mod_n a pre-created Modular_Reducer for n
89* @param rng a random number generator
90* @param t number of tests to perform
91*
92* @return result of primality test
93*/
95 const Modular_Reducer& mod_n,
96 RandomNumberGenerator& rng,
97 size_t t);
98
99/**
100* Generate DSA parameters using the FIPS 186 kosherizer
101* @param rng a random number generator
102* @param p_out where the prime p will be stored
103* @param q_out where the prime q will be stored
104* @param pbits how long p will be in bits
105* @param qbits how long q will be in bits
106* @return random seed used to generate this parameter set
107*/
108std::vector<uint8_t> generate_dsa_primes(
109 RandomNumberGenerator& rng, BigInt& p_out, BigInt& q_out, size_t pbits, size_t qbits);
110
111/**
112* Generate DSA parameters using the FIPS 186 kosherizer
113* @param rng a random number generator
114* @param p_out where the prime p will be stored
115* @param q_out where the prime q will be stored
116* @param pbits how long p will be in bits
117* @param qbits how long q will be in bits
118* @param seed the seed used to generate the parameters
119* @param offset optional offset from seed to start searching at
120* @return true if seed generated a valid DSA parameter set, otherwise
121 false. p_out and q_out are only valid if true was returned.
122*/
123bool BOTAN_TEST_API generate_dsa_primes(RandomNumberGenerator& rng,
124 BigInt& p_out,
125 BigInt& q_out,
126 size_t pbits,
127 size_t qbits,
128 const std::vector<uint8_t>& seed,
129 size_t offset = 0);
130
131} // namespace Botan
132
133#endif
#define BOTAN_TEST_API
Definition compiler.h:51
bool passes_miller_rabin_test(const BigInt &n, const Modular_Reducer &mod_n, const std::shared_ptr< Montgomery_Params > &monty_n, const BigInt &a)
bool is_miller_rabin_probable_prime(const BigInt &n, const Modular_Reducer &mod_n, RandomNumberGenerator &rng, size_t test_iterations)
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:53
bool is_bailie_psw_probable_prime(const BigInt &n, const Modular_Reducer &mod_n)
Definition primality.cpp:89
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
bool is_lucas_probable_prime(const BigInt &C, const Modular_Reducer &mod_C)
Definition primality.cpp:18