8#include <botan/internal/primality.h>
10#include <botan/exceptn.h>
11#include <botan/numthry.h>
13#include <botan/internal/bit_ops.h>
14#include <botan/internal/ct_utils.h>
15#include <botan/internal/loadstor.h>
16#include <botan/internal/monty.h>
23class Prime_Sieve final {
25 Prime_Sieve(
const BigInt& init_value,
size_t sieve_size,
word step,
bool check_2p1) :
28 m_check_2p1(check_2p1) {}
30 size_t sieve_size()
const {
return m_sieve.size(); }
32 bool check_2p1()
const {
return m_check_2p1; }
36 for(
size_t i = 0; i != m_sieve.size(); ++i) {
37 m_sieve[i] = sieve_step_incr(m_sieve[i], m_step,
PRIMES[i]);
42 if(this->check_2p1()) {
52 passes &= ~CT::Mask<word>::is_equal(m_sieve[i], (
PRIMES[i] - 1) / 2);
56 return passes.as_bool();
60 void add(uint64_t r) {
62 for(
size_t i = 0; i != m_sieve.size(); ++i) {
63 const word next = m_sieve[i] + r_mod[i];
75 const word stepmod = (step >= mod) ? (step % mod) : step;
78 const word next = (v + stepmod);
82 std::vector<word> m_sieve;
84 const bool m_check_2p1;
87#if defined(BOTAN_ENABLE_DEBUG_ASSERTS)
89bool no_small_multiples(
const BigInt& v,
const Prime_Sieve& sieve) {
90 const size_t sieve_size = sieve.sieve_size();
91 const bool check_2p1 = sieve.check_2p1();
96 const BigInt v_x2_p1 = 2 * v + 1;
98 for(
size_t i = 0; i != sieve_size; ++i) {
103 if(v_x2_p1 %
PRIMES[i] == 0)
119 bool sieve_check_2p1) {
120 const size_t MAX_ATTEMPTS = 32 * 1024;
125 if(std::gcd(equiv, modulo) != 1) {
126 throw Invalid_Argument(
"random_prime equiv and modulo must be relatively prime");
138 p += (modulo - (p % modulo)) + equiv;
140 Prime_Sieve sieve(p, bits, modulo, sieve_check_2p1);
142 for(
size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) {
171 if(
gcd(p - 1, coprime) > 1) {
176 if(p.bits() > bits) {
201 throw Invalid_Argument(
"random_prime: Can't make a prime of " + std::to_string(bits) +
" bits");
207 if(modulo == 0 || modulo >= 100000) {
221 if(equiv != 1 || modulo != 2 || coprime != 0) {
222 throw Not_Implemented(
"random_prime equiv/modulo/coprime options not usable for small primes");
227 }
else if(bits == 3) {
229 }
else if(bits == 4) {
237 const uint16_t small_prime =
PRIMES[idx];
249 return random_prime_with_sieve(rng, bits, coprime, equiv, modulo, prob,
false);
266 if(coprime <= 1 || coprime.
is_even() || coprime.
bits() > 64) {
267 throw Invalid_Argument(
"generate_rsa_prime coprime must be small odd positive integer");
270 const size_t MAX_ATTEMPTS = 32 * 1024;
275 BigInt p(keygen_rng, bits);
294 Prime_Sieve sieve(p, bits, step,
false);
302 const auto skip_ahead = [&]() {
311 for(
size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) {
335 if(
gcd(p - 1, coprime) > 1) {
340 if(p.
bits() > bits) {
358 throw Invalid_Argument(
"random_safe_prime: Can't make a prime of " + std::to_string(bits) +
" bits");
361 const size_t error_bound = 128;
370 q = random_prime_with_sieve(rng, bits - 1,
BigInt::zero(), 2, 3, error_bound,
true);
373 if(
is_prime(p, rng, error_bound,
true)) {
#define BOTAN_DEBUG_ASSERT(expr)
static BigInt from_u64(uint64_t n)
static BigInt from_word(word n)
static constexpr Mask< T > is_gte(T x, T y)
static constexpr Mask< T > set()
static constexpr Mask< T > expand(T v)
void randomize(std::span< uint8_t > output)
std::array< uint8_t, bytes > random_array()
constexpr auto scoped_poison(const Ts &... xs)
constexpr void poison(const T *p, size_t n)
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo, size_t prob)
const size_t PRIME_TABLE_SIZE
std::vector< word > BOTAN_TEST_API mod_small_primes(const BigInt &n, size_t num_primes)
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
BigInt generate_rsa_prime(RandomNumberGenerator &keygen_rng, RandomNumberGenerator &prime_test_rng, size_t bits, const BigInt &coprime, size_t prob)
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
BigInt gcd(const BigInt &a, const BigInt &b)
constexpr auto load_le(ParamTs &&... params)
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)
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
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)