8 #include <botan/numthry.h> 9 #include <botan/pow_mod.h> 10 #include <botan/reducer.h> 11 #include <botan/monty.h> 12 #include <botan/divide.h> 13 #include <botan/rng.h> 14 #include <botan/internal/bit_ops.h> 15 #include <botan/internal/mp_core.h> 16 #include <botan/internal/ct_utils.h> 17 #include <botan/internal/monty_exp.h> 18 #include <botan/internal/primality.h> 32 for(
size_t i = 0; i != n.
size(); ++i)
42 low_zero += BOTAN_MP_WORD_BITS;
68 while(
X[0].is_nonzero())
73 const uint8_t sel =
static_cast<uint8_t
>(
X[0] >=
X[1]);
79 return (
X[1] << shift);
108 BigInt u = p, v = a, r = 0, s = 1;
155 for(
size_t i = 0; i != k; ++i)
168 throw Invalid_Argument(
"ct_inverse_mod_odd_modulus: arguments must be non-negative");
172 throw Invalid_Argument(
"ct_inverse_mod_odd_modulus n >= mod not supported");
194 BigInt mp1o2 = (mod + 1) >> 1;
196 const size_t mod_words = mod.
sig_words();
205 v.grow_to(mod_words);
219 size_t bits = 2 * mod.
bits();
246 const word odd_a = a_w[0] & 1;
249 word underflow =
bigint_cnd_sub(odd_a, a_w.data(), b_w.data(), mod_words);
260 word borrow =
bigint_cnd_sub(odd_a, u_w.data(), v_w.data(), mod_words);
265 const word odd_u = u_w[0] & 1;
299 if(mod.
is_odd() && n < mod)
316 BigInt A = 1, B = 0, C = 0, D = 1;
327 const bool u_gte_v = (u >= v);
329 for(
size_t i = 0; i != u_zero_bits; ++i)
331 const bool needs_adjust = A.
is_odd() || B.is_odd();
337 B.ct_cond_assign(needs_adjust, T1);
343 for(
size_t i = 0; i != v_zero_bits; ++i)
345 const bool needs_adjust = C.
is_odd() || D.is_odd();
350 D.ct_cond_assign(needs_adjust, T1);
366 B.ct_cond_assign(u_gte_v, T2);
368 v.ct_cond_assign(!u_gte_v, T0);
369 C.ct_cond_assign(!u_gte_v, T1);
370 D.ct_cond_assign(!u_gte_v, T2);
376 while(D.is_negative())
397 for(
size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i)
399 const word bi = b % 2;
401 r += bi << (BOTAN_MP_WORD_BITS - 1);
445 return (mod - pow_mod.
execute());
463 const size_t n = C.
bits();
464 const size_t m = (n + 1) / 2;
472 X = (X2 + C) / (2*
X);
498 const size_t n_bits = n.
bits();
503 const uint16_t num =
static_cast<uint16_t
>(n.
word_at(0));
const size_t PRIME_TABLE_SIZE
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
bool is_lucas_probable_prime(const BigInt &C, const Modular_Reducer &mod_C)
size_t low_zero_bits(const BigInt &n)
BigInt gcd(const BigInt &a, const BigInt &b)
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
BigInt inverse_euclid(const BigInt &n, const BigInt &mod)
secure_vector< word > & get_word_vector()
BigInt ct_inverse_mod_odd_modulus(const BigInt &n, const BigInt &mod)
BigInt normalized_montgomery_inverse(const BigInt &a, const BigInt &p)
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
void poison(const T *p, size_t n)
word word_at(size_t n) const
const word * data() const
#define BOTAN_ASSERT(expr, assertion_made)
void set_exponent(const BigInt &exponent) const
bool is_bailie_psw_probable_prime(const BigInt &n, const Modular_Reducer &mod_n)
word bigint_cnd_sub(word cnd, word x[], size_t x_size, const word y[], size_t y_size)
BigInt lcm(const BigInt &a, const BigInt &b)
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
BigInt is_perfect_square(const BigInt &C)
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
word bigint_cnd_add(word cnd, word x[], word x_size, const word y[], size_t y_size)
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
static BigInt power_of_2(size_t n)
void cond_flip_sign(bool predicate)
word monty_inverse(word a)
void grow_to(size_t n) const
virtual bool is_seeded() const =0
size_t almost_montgomery_inverse(BigInt &result, const BigInt &a, const BigInt &p)
bool is_miller_rabin_probable_prime(const BigInt &n, const Modular_Reducer &mod_n, RandomNumberGenerator &rng, size_t test_iterations)
void unpoison(const T *p, size_t n)
std::vector< T, secure_allocator< T > > secure_vector
void bigint_cnd_abs(word cnd, word x[], size_t size)
void set_base(const BigInt &base) const
void ct_cond_assign(bool predicate, const BigInt &other)