9#include <botan/numthry.h>
12#include <botan/internal/barrett.h>
13#include <botan/internal/ct_utils.h>
14#include <botan/internal/divide.h>
15#include <botan/internal/monty.h>
16#include <botan/internal/monty_exp.h>
17#include <botan/internal/mp_core.h>
18#include <botan/internal/primality.h>
32 if(p == 2 || a <= 1) {
59 r = mod_p.multiply(r, a);
101 r = mod_p.multiply(r, c);
103 n = mod_p.multiply(n, c);
139 if(shifts % 2 == 1) {
140 word y_mod_8 = y % 8;
141 if(y_mod_8 == 3 || y_mod_8 == 5) {
146 if(x % 4 == 3 && y % 4 == 3) {
172 for(
size_t i = 0; i != n.
size(); ++i) {
176 const size_t tz_x =
ctz(x);
180 low_zero += seen_nonempty_word.if_not_set_return(tz_x);
187 return static_cast<size_t>(seen_nonempty_word.if_set_return(low_zero));
214 const size_t loop_cnt = u.bits() + v.bits();
222 size_t factors_of_two = 0;
223 for(
size_t i = 0; i != loop_cnt; ++i) {
228 bigint_sub_abs(tmp.mutable_data(), u._data(), v._data(), sz, ws.data());
229 u.ct_cond_assign((u_gt_v & both_odd).as_bool(), tmp);
230 v.ct_cond_assign((~u_gt_v & both_odd).as_bool(), tmp);
238 factors_of_two += (u_is_even & v_is_even).if_set_return(1);
242 u.ct_cond_assign(u_is_even.as_bool(), tmp);
246 v.ct_cond_assign(v_is_even.as_bool(), tmp);
256 u.ct_cond_assign(u.is_even() , v);
259 u.ct_shift_left(factors_of_two);
276 const auto g =
gcd(a, b);
297 const size_t exp_bits = exp.
bits();
312 for(
size_t i = 0; i != exp_bits; ++i) {
328 const size_t n = C.
bits();
329 const size_t m = (n + 1) / 2;
336 X = (X2 + C) / (2 * X);
362 const size_t n_bits = n.
bits();
366 const uint16_t num =
static_cast<uint16_t
>(n.
word_at(0));
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ARG_CHECK(expr, msg)
static Barrett_Reduction for_public_modulus(const BigInt &m)
static Barrett_Reduction for_secret_modulus(const BigInt &m)
void ct_cond_assign(bool predicate, const BigInt &other)
word word_at(size_t n) const
static BigInt power_of_2(size_t n)
static BigInt from_s32(int32_t n)
static BigInt from_word(word n)
BigInt & square(secure_vector< word > &ws)
bool get_bit(size_t n) const
static BigInt with_capacity(size_t n)
static constexpr Mask< T > expand(T v)
static constexpr Mask< T > expand_bool(bool v)
static constexpr Mask< T > cleared()
virtual bool is_seeded() const =0
constexpr void poison_all(const Ts &... ts)
constexpr void unpoison_all(const Ts &... ts)
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
constexpr void bigint_shr2(W y[], const W x[], size_t x_size, size_t shift)
Montgomery_Int monty_exp_vartime(const Montgomery_Params ¶ms_p, const BigInt &g, const BigInt &k)
bool is_lucas_probable_prime(const BigInt &C, const Barrett_Reduction &mod_C)
BigInt lcm(const BigInt &a, const BigInt &b)
BigInt square(const BigInt &x)
size_t low_zero_bits(const BigInt &n)
BigInt abs(const BigInt &n)
const size_t PRIME_TABLE_SIZE
bool is_bailie_psw_probable_prime(const BigInt &n, const Barrett_Reduction &mod_n)
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
BigInt ct_modulo(const BigInt &x, const BigInt &y)
constexpr int32_t bigint_cmp(const W x[], size_t x_size, const W y[], size_t y_size)
consteval std::array< W, N > reduce_mod(const std::array< W, XN > &x, const std::array< W, N > &p)
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
constexpr auto bigint_sub_abs(W z[], const W x[], const W y[], size_t N, W ws[]) -> CT::Mask< W >
BigInt gcd(const BigInt &a, const BigInt &b)
std::vector< T, secure_allocator< T > > secure_vector
BigInt sqrt_modulo_prime(const BigInt &a, const BigInt &p)
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_miller_rabin_probable_prime(const BigInt &n, const Barrett_Reduction &mod_n, RandomNumberGenerator &rng, size_t test_iterations)
BOTAN_FORCE_INLINE constexpr size_t ctz(T n)
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Montgomery_Int monty_exp(const Montgomery_Params ¶ms_p, const BigInt &g, const BigInt &k, size_t max_k_bits)