Botan 2.19.3
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
13namespace Botan {
14
15class BigInt;
16class Modular_Reducer;
17class Montgomery_Params;
18class 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*/
31bool 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*/
44bool 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*/
56bool 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*/
67size_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*/
78bool 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
#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 is_bailie_psw_probable_prime(const BigInt &n, const Modular_Reducer &mod_n)
Definition primality.cpp:92
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:17