7#include <botan/internal/primality.h>
9#include <botan/bigint.h>
10#include <botan/numthry.h>
11#include <botan/reducer.h>
13#include <botan/internal/monty.h>
14#include <botan/internal/monty_exp.h>
20 if(C == 2 || C == 3 || C == 5 || C == 7 || C == 11 || C == 13) {
55 const size_t K_bits = K.bits() - 1;
62 for(
size_t i = 0; i != K_bits; ++i) {
63 const bool k_bit = K.get_bit(K_bits - 1 - i);
75 U2 = mod_C.
reduce(Ut + Vt);
79 V2 = mod_C.
reduce(Vt + Ut * D);
93 }
else if(n <= 1 || n.
is_even()) {
97 auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n);
104 const std::shared_ptr<Montgomery_Params>& monty_n,
112 const BigInt n_minus_1 = n - 1;
114 const BigInt nm1_s = n_minus_1 >> s;
115 const size_t n_bits = n.
bits();
117 const size_t powm_window = 4;
123 if(y == 1 || y == n_minus_1) {
127 for(
size_t i = 1; i != s; ++i) {
149 size_t test_iterations) {
154 auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n);
156 for(
size_t i = 0; i != test_iterations; ++i) {
169 const size_t base = (prob + 2) / 2;
175 if(random ==
false) {
#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)
static BigInt from_word(word n)
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)
bool is_bailie_psw_probable_prime(const BigInt &n, const Modular_Reducer &mod_n)
Montgomery_Int monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
BigInt is_perfect_square(const BigInt &C)
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(const Montgomery_Int &g, size_t window_bits, bool const_time)
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)