7#include <botan/internal/primality.h>
9#include <botan/bigint.h>
10#include <botan/numthry.h>
12#include <botan/internal/bit_ops.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/target_info.h>
22#if defined(BOTAN_HAS_THREAD_UTILS) && !defined(BOTAN_HAS_VALGRIND)
23 #include <botan/internal/thread_pool.h>
40 const size_t iterations = 2 *
high_bit(n);
44 for(
size_t i = 0; i != iterations; ++i) {
49 s ^= swap.if_set_return(a & n & 2);
50 swap.conditional_swap(a, n);
52 a -= a_odd.if_set_return(n);
56 s ^= (n ^ (n >> 1)) & 2;
75 for(
size_t i = first; i != first + count; ++i) {
76 const word d = 5 + 2 * i;
81 const auto [minus_one, zero] = ct_jacobi_word(r, d);
83 const auto first_hit = ~found & (minus_one | zero);
84 index = first_hit.select(
static_cast<word>(i), index);
85 symbol_zero |= first_hit & zero;
89 return {found, symbol_zero, index};
99 if(C == 2 || C == 3 || C == 5 || C == 7 || C == 11 || C == 13) {
114 const size_t block = vartime ? 8 : 256;
117 for(
size_t first = 0;; first += block) {
118 const auto [found, symbol_zero, index] = selfridge_search(C, first, block);
120 if(found.as_bool()) {
121 if(symbol_zero.as_bool()) {
138 const word D = 5 + 2 * D_index;
139 const bool D_negative = (D_index % 2) == 1;
142 const size_t K_bits = K.
bits() - 1;
164 t.ct_cond_negate(D_negative);
169 for(
size_t i = 0; i != K_bits; ++i) {
170 const bool k_bit = K.get_bit(K_bits - 1 - i);
178 T.square_this_n_times(ws, 1);
180 Vt.square_this_n_times(ws, 1);
184 if(!vartime || k_bit) {
208 U.ct_cond_assign(k_bit, U2);
209 V.ct_cond_assign(k_bit, V2);
219size_t vartime_window_bits(
size_t exp_bits) {
220 if(exp_bits <= 256) {
222 }
else if(exp_bits <= 1024) {
224 }
else if(exp_bits <= 2048) {
234class Miller_Rabin_Test final {
236 Miller_Rabin_Test(
const BigInt& n,
const Montgomery_Params& monty_n,
bool vartime) :
237 m_monty_n(monty_n), m_vartime(vartime) {
240 const size_t N = m_monty_n.p_words();
242 const BigInt n_minus_1 = n - 1;
250 m_d = n_minus_1 >> m_s;
251 m_d_bits = m_d.bits();
254 m_one.assign(m_monty_n.R1()._as_span().first(N).begin(), m_monty_n.R1()._as_span().first(N).end());
255 m_minus_one.resize(N);
256 bigint_sub3(m_minus_one.data(), n._data(), N, m_one.data(), N);
262 bool passes(
const BigInt& a)
const {
263 Montgomery_Int y = [&]() {
265 const auto powm_a =
monty_precompute(m_monty_n, a, vartime_window_bits(m_d_bits));
273 if(is_one(y) || is_minus_one(y)) {
279 for(
size_t i = 1; i != m_s; ++i) {
280 y.square_this_n_times(ws, 1);
290 if(is_minus_one(y)) {
299 bool is_one(
const Montgomery_Int& y)
const {
300 return CT::is_equal(y.repr().data(), m_one.data(), m_one.size()).as_bool();
303 bool is_minus_one(
const Montgomery_Int& y)
const {
304 return CT::is_equal(y.repr().data(), m_minus_one.data(), m_minus_one.size()).as_bool();
307 Montgomery_Params m_monty_n;
316bool miller_rabin_test(
const BigInt& n,
319 size_t test_iterations,
325 const Miller_Rabin_Test mr(n, monty_n, vartime);
327 for(
size_t i = 0; i != test_iterations; ++i) {
339#if defined(BOTAN_HAS_THREAD_UTILS) && !defined(BOTAN_HAS_VALGRIND)
347size_t miller_rabin_tests_per_job(
size_t n_bits) {
348 constexpr size_t ref_bits = 1024;
349 constexpr size_t ref_tests = 8;
350 if(n_bits > ref_bits) {
353 return std::max(ref_tests, (ref_tests * ref_bits * ref_bits) / (n_bits * n_bits));
359bool miller_rabin_lucas_test(
368 const Miller_Rabin_Test mr(n, monty_n, vartime);
373 if(!mr.passes(random_base())) {
378#if defined(BOTAN_HAS_THREAD_UTILS) && !defined(BOTAN_HAS_VALGRIND)
380 const size_t tests_per_job = miller_rabin_tests_per_job(n.bits());
383 if(pool.worker_count() > 0 && t > 0 && t + 3 >= tests_per_job) {
385 std::vector<BigInt> bases;
387 for(
size_t i = 0; i != t; ++i) {
388 bases.push_back(random_base());
395 const auto passes_tests = [&](
size_t from,
size_t to) {
396 for(
size_t i = from; i != to; ++i) {
397 if(!mr.passes(bases[i])) {
404 std::vector<Joining_Future<bool>> futures;
405 futures.reserve(jobs);
407 futures.push_back(pool.run([&]() { return lucas_test(n, monty_n, vartime); }));
410 for(
size_t j = 1; j < jobs; ++j) {
411 const size_t from = j * job_tests;
412 const size_t to = std::min(t, from + job_tests);
413 futures.push_back(pool.run([&, from, to]() { return passes_tests(from, to); }));
416 bool passes = passes_tests(0, std::min(t, job_tests));
419 for(
auto& future : futures) {
420 passes = future.get() && passes;
427 for(
size_t i = 0; i != t; ++i) {
428 if(!mr.passes(random_base())) {
433 return lucas_test(n, monty_n, vartime);
443 const Miller_Rabin_Test mr(n, monty_n, vartime);
450 return lucas_test(n, monty_n,
false);
454 return lucas_test(n, monty_n,
true);
458 return bailie_psw_test(n, monty_n,
false);
462 return bailie_psw_test(n, monty_n,
true);
478 }
else if(n <= 1 || n.
is_even()) {
488 size_t test_iterations) {
489 return miller_rabin_test(n, monty_n, rng, test_iterations,
false);
495 size_t test_iterations) {
496 return miller_rabin_test(n, monty_n, rng, test_iterations,
true);
502 size_t test_iterations) {
503 return miller_rabin_lucas_test(n, monty_n, rng, test_iterations,
false);
509 size_t test_iterations) {
510 return miller_rabin_lucas_test(n, monty_n, rng, test_iterations,
true);
517 prob = std::min<size_t>(512, prob);
519 const size_t base = (prob + 2) / 2;
#define BOTAN_ARG_CHECK(expr, msg)
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
static BigInt from_word(word n)
static constexpr Mask< T > expand_bit(T v, size_t bit)
static constexpr Mask< T > expand(T v)
static constexpr Mask< T > is_equal(T x, T y)
static constexpr Mask< T > is_lt(T x, T y)
static constexpr Mask< T > cleared()
static Montgomery_Int one(const Montgomery_Params ¶ms)
static Thread_Pool & global_instance()
constexpr decltype(auto) driveby_unpoison(T &&v)
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
constexpr void unpoison(const T *p, size_t n)
constexpr void poison(const T *p, size_t n)
word ct_mod_word(const BigInt &x, word y)
bool is_miller_rabin_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n, RandomNumberGenerator &rng, size_t test_iterations)
BOTAN_FORCE_INLINE constexpr T ceil_division(T a, T b)
bool is_bailie_psw_probable_prime(const BigInt &n, const Montgomery_Params &monty_n)
size_t low_zero_bits(const BigInt &n)
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
bool is_bailie_psw_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n)
std::shared_ptr< const Montgomery_Exponentiation_State > monty_precompute(const Montgomery_Int &g, size_t window_bits)
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
Montgomery_Int monty_execute_vartime(const Montgomery_Exponentiation_State &precomputed_state, const BigInt &k)
bool is_lucas_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n)
std::vector< T, secure_allocator< T > > secure_vector
BigInt is_perfect_square(const BigInt &C)
bool is_miller_rabin_lucas_probable_prime(const BigInt &n, const Montgomery_Params &monty_n, RandomNumberGenerator &rng, size_t test_iterations)
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
bool is_miller_rabin_probable_prime(const BigInt &n, const Montgomery_Params &monty_n, RandomNumberGenerator &rng, size_t test_iterations)
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
bool is_lucas_probable_prime(const BigInt &n, const Montgomery_Params &monty_n)
bool is_miller_rabin_lucas_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n, RandomNumberGenerator &rng, size_t test_iterations)
Montgomery_Int monty_execute(const Montgomery_Exponentiation_State &precomputed_state, const BigInt &k, size_t max_k_bits)