8#include <botan/numthry.h>
9#include <botan/reducer.h>
10#include <botan/monty.h>
11#include <botan/divide.h>
13#include <botan/internal/ct_utils.h>
14#include <botan/internal/mp_core.h>
15#include <botan/internal/monty_exp.h>
16#include <botan/internal/primality.h>
23void sub_abs(BigInt& z,
const BigInt& x,
const BigInt& y)
25 const size_t x_sw = x.sig_words();
26 const size_t y_sw = y.sig_words();
27 z.resize(std::max(x_sw, y_sw));
45 for(
size_t i = 0; i != n.
size(); ++i)
50 const size_t tz_x =
ctz(x);
54 low_zero += seen_nonempty_word.if_not_set_return(tz_x);
61 return seen_nonempty_word.if_set_return(low_zero);
66size_t safegcd_loop_bound(
size_t f_bits,
size_t g_bits)
68 const size_t d = std::max(f_bits, g_bits);
71 return (49*d + 80) / 17;
73 return (49*d + 57) / 17;
110 const size_t loop_cnt = safegcd_loop_bound(f.
bits(), g.
bits());
113 for(
size_t i = 0; i != loop_cnt; ++i)
117 const bool need_swap = (g.
is_odd() && delta > 0);
167 const size_t exp_bits = exp.
bits();
171 const size_t powm_window = 4;
173 auto monty_mod = std::make_shared<Montgomery_Params>(mod, reduce_mod);
186 for(
size_t i = 0; i != exp_bits; ++i)
203 const size_t n = C.
bits();
204 const size_t m = (n + 1) / 2;
212 X = (X2 + C) / (2*
X);
238 const size_t n_bits = n.
bits();
243 const uint16_t num =
static_cast<uint16_t
>(n.
word_at(0));
#define BOTAN_ASSERT_NOMSG(expr)
void ct_cond_add(bool predicate, const BigInt &value)
void ct_cond_assign(bool predicate, const BigInt &other)
word word_at(size_t n) const
static BigInt power_of_2(size_t n)
void const_time_poison() const
void ct_cond_swap(bool predicate, BigInt &other)
void const_time_unpoison() const
bool get_bit(size_t n) const
static Mask< T > expand(T v)
static Mask< T > cleared()
BigInt square(const BigInt &x) const
BigInt multiply(const BigInt &x, const BigInt &y) const
BigInt reduce(const BigInt &x) const
virtual bool is_seeded() const =0
void unpoison(const T *p, size_t n)
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
BigInt lcm(const BigInt &a, const BigInt &b)
size_t low_zero_bits(const BigInt &n)
BigInt abs(const BigInt &n)
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
const size_t PRIME_TABLE_SIZE
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
bool is_miller_rabin_probable_prime(const BigInt &n, const Modular_Reducer &mod_n, RandomNumberGenerator &rng, size_t test_iterations)
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
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 gcd(const BigInt &a, const BigInt &b)
BigInt is_perfect_square(const BigInt &C)
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)
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)