8 #include <botan/numthry.h>
9 #include <botan/reducer.h>
10 #include <botan/internal/bit_ops.h>
11 #include <botan/internal/mp_core.h>
12 #include <botan/internal/ct_utils.h>
26 for(
size_t i = 0; i != n.
size(); ++i)
36 low_zero += BOTAN_MP_WORD_BITS;
49 if(a == 1 || b == 1)
return 1;
63 if(x >= y) { x -= y; x >>= 1; }
64 else { y -= x; y >>= 1; }
75 return ((a * b) /
gcd(a, b));
96 BigInt u = p, v = a, r = 0, s = 1;
143 for(
size_t i = 0; i != k; ++i)
156 throw Invalid_Argument(
"ct_inverse_mod_odd_modulus: arguments must be non-negative");
180 BigInt mp1o2 = (mod + 1) >> 1;
182 const size_t mod_words = mod.
sig_words();
191 v.grow_to(mod_words);
205 size_t bits = 2 * mod.
bits();
232 const word odd_a = a_w[0] & 1;
235 word underflow =
bigint_cnd_sub(odd_a, a_w.data(), b_w.data(), mod_words);
246 word borrow =
bigint_cnd_sub(odd_a, u_w.data(), v_w.data(), mod_words);
251 const word odd_u = u_w[0] & 1;
290 BigInt A = 1, B = 0, C = 0, D = 1;
296 for(
size_t i = 0; i != u_zero_bits; ++i)
298 if(A.
is_odd() || B.is_odd())
299 { A += n; B -= mod; }
305 for(
size_t i = 0; i != v_zero_bits; ++i)
307 if(C.is_odd() || D.is_odd())
308 { C += n; D -= mod; }
312 if(u >= v) { u -= v; A -= C; B -= D; }
313 else { v -= u; C -= A; D -= B; }
319 while(D.is_negative()) D += mod;
320 while(D >= mod) D -= mod;
328 throw Exception(
"monty_inverse: divide by zero");
331 word x2 = 1, x1 = 0, y2 = 0, y1 = 1;
361 const word check = y2 * input;
389 bool mr_witness(BigInt&& y,
390 const Modular_Reducer& reducer_n,
391 const BigInt& n_minus_1,
size_t s)
393 if(y == 1 || y == n_minus_1)
396 for(
size_t i = 1; i != s; ++i)
398 y = reducer_n.square(y);
410 size_t mr_test_iterations(
size_t n_bits,
size_t prob,
bool random)
412 const size_t base = (prob + 2) / 2;
421 if(random && prob <= 80)
442 size_t prob,
bool is_random)
452 const uint16_t num =
static_cast<uint16_t
>(n.
word_at(0));
457 const size_t test_iterations = mr_test_iterations(n.
bits(), prob, is_random);
459 const BigInt n_minus_1 = n - 1;
465 for(
size_t i = 0; i != test_iterations; ++i)
470 if(mr_witness(std::move(y), reducer, n_minus_1, s))
const size_t PRIME_TABLE_SIZE
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
word word_at(size_t n) const
BigInt normalized_montgomery_inverse(const BigInt &a, const BigInt &p)
const uint16_t BOTAN_DLL PRIMES[]
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
BigInt gcd(const BigInt &a, const BigInt &b)
secure_vector< word > & get_word_vector()
void poison(const T *p, size_t n)
word bigint_divop(word n1, word n0, word d)
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
#define BOTAN_ASSERT(expr, assertion_made)
std::vector< T, secure_allocator< T >> secure_vector
size_t almost_montgomery_inverse(BigInt &result, const BigInt &a, const BigInt &p)
BigInt ct_inverse_mod_odd_modulus(const BigInt &n, const BigInt &mod)
#define BOTAN_ASSERT_EQUAL(expr1, expr2, assertion_made)
void set_exponent(const BigInt &exponent) const
word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
const word * data() const
void bigint_cnd_abs(word cnd, word x[], size_t size)
size_t low_zero_bits(const BigInt &n)
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
word monty_inverse(word input)
void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
void unpoison(const T *p, size_t n)
void set_base(const BigInt &base) const
BigInt lcm(const BigInt &a, const BigInt &b)