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>
30 for(
size_t i = 0; i != n.
size(); ++i)
35 const size_t tz_x =
ctz(x);
39 low_zero += seen_nonempty_word.if_not_set_return(tz_x);
46 return seen_nonempty_word.if_set_return(low_zero);
69 v.const_time_poison();
76 const size_t loop_cnt = u.bits() + v.bits();
85 size_t factors_of_two = 0;
86 for(
size_t i = 0; i != loop_cnt; ++i) {
87 auto both_odd = WordMask::expand(u.is_odd()) & WordMask::expand(v.is_odd());
90 auto u_gt_v = WordMask::expand(
bigint_cmp(u.data(), u.size(), v.data(), v.size()) > 0);
92 u.ct_cond_assign((u_gt_v & both_odd).is_set(), tmp);
93 v.ct_cond_assign((~u_gt_v & both_odd).is_set(), tmp);
95 const auto u_is_even = WordMask::expand(u.is_even());
96 const auto v_is_even = WordMask::expand(v.is_even());
101 factors_of_two += (u_is_even & v_is_even).if_set_return(1);
104 bigint_shr2(tmp.mutable_data(), u.data(), sz, 0, 1);
105 u.ct_cond_assign(u_is_even.is_set(), tmp);
108 bigint_shr2(tmp.mutable_data(), v.data(), sz, 0, 1);
109 v.ct_cond_assign(v_is_even.is_set(), tmp);
119 u.ct_cond_assign(u.is_even() , v);
122 u.ct_shift_left(factors_of_two);
124 u.const_time_unpoison();
125 v.const_time_unpoison();
157 const size_t exp_bits = exp.
bits();
161 const size_t powm_window = 4;
163 auto monty_mod = std::make_shared<Montgomery_Params>(mod, reduce_mod);
176 for(
size_t i = 0; i != exp_bits; ++i)
193 const size_t n = C.
bits();
194 const size_t m = (n + 1) / 2;
202 X = (X2 + C) / (2*
X);
228 const size_t n_bits = n.
bits();
233 const uint16_t num =
static_cast<uint16_t
>(n.
word_at(0));
#define BOTAN_DEBUG_ASSERT(expr)
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
bool get_bit(size_t n) const
static BigInt with_capacity(size_t n)
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
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)
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
BigInt is_perfect_square(const BigInt &C)
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
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)