7#include <botan/internal/primality.h>
8#include <botan/internal/monty_exp.h>
9#include <botan/bigint.h>
10#include <botan/monty.h>
11#include <botan/reducer.h>
25 else if(C == 3 || C == 5 || C == 7 || C == 11 || C == 13)
56 const size_t K_bits = K.
bits() - 1;
63 for(
size_t i = 0; i != K_bits; ++i)
65 const bool k_bit = K.
get_bit(K_bits - 1 - i);
77 U2 = mod_C.
reduce(Ut + Vt);
81 V2 = mod_C.
reduce(Vt + Ut*D);
94 auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n);
106 const std::shared_ptr<Montgomery_Params>& monty_n,
111 const BigInt n_minus_1 = n - 1;
113 const BigInt nm1_s = n_minus_1 >> s;
114 const size_t n_bits = n.
bits();
116 const size_t powm_window = 4;
122 if(y == 1 || y == n_minus_1)
125 for(
size_t i = 1; i != s; ++i)
146 size_t test_iterations)
150 auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n);
152 for(
size_t i = 0; i != test_iterations; ++i)
167 const size_t base = (prob + 2) / 2;
#define BOTAN_ASSERT_NOMSG(expr)
void ct_cond_add(bool predicate, const BigInt &value)
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
void ct_cond_assign(bool predicate, const BigInt &other)
bool get_bit(size_t n) const
BigInt square(const BigInt &x) const
BigInt multiply(const BigInt &x, const BigInt &y) const
BigInt reduce(const BigInt &x) const
size_t low_zero_bits(const BigInt &n)
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)
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(std::shared_ptr< const Montgomery_Params > params, const BigInt &g, size_t window_bits, bool const_time)
bool is_bailie_psw_probable_prime(const BigInt &n, const Modular_Reducer &mod_n)
BigInt is_perfect_square(const BigInt &C)
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
int32_t jacobi(const BigInt &a, const BigInt &n)
bool is_lucas_probable_prime(const BigInt &C, const Modular_Reducer &mod_C)
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)