8 #include <botan/numthry.h>
9 #include <botan/reducer.h>
10 #include <botan/internal/bit_ops.h>
20 class MillerRabin_Test
23 bool is_witness(
const BigInt& nonce);
24 MillerRabin_Test(
const BigInt& num);
36 bool MillerRabin_Test::is_witness(
const BigInt& a)
45 for(
size_t i = 1; i !=
s; ++i)
63 MillerRabin_Test::MillerRabin_Test(
const BigInt& num)
65 if(num.is_even() || num < 3)
80 size_t miller_rabin_test_iterations(
size_t bits,
size_t level)
82 struct mapping {
size_t bits;
size_t verify_iter;
size_t check_iter; };
84 static const mapping tests[] = {
120 for(
size_t i = 0; tests[i].bits; ++i)
122 if(bits <= tests[i].bits)
125 return tests[i].verify_iter;
127 return tests[i].check_iter;
129 return std::max<size_t>(tests[i].check_iter / 4, 1);
133 return level > 0 ? 2 : 1;
147 for(
size_t i = 0; i != n.
size(); ++i)
157 low_zero += BOTAN_MP_WORD_BITS;
170 if(a == 1 || b == 1)
return 1;
184 if(x >= y) { x -= y; x >>= 1; }
185 else { y -= x; y >>= 1; }
196 return ((a * b) /
gcd(a, b));
213 BigInt A = 1, B = 0, C = 0, D = 1;
215 while(u.is_nonzero())
219 for(
size_t i = 0; i != zero_bits; ++i)
221 if(A.
is_odd() || B.is_odd())
228 for(
size_t i = 0; i != zero_bits; ++i)
230 if(C.is_odd() || D.is_odd())
235 if(u >= v) { u -= v; A -= C; B -= D; }
236 else { v -= u; C -= A; D -= B; }
242 while(D.is_negative()) D += mod;
243 while(D >= mod) D -=
mod;
266 const size_t PREF_NONCE_BITS = 128;
278 for(
size_t i = 0;
PRIMES[i]; ++i)
292 const size_t NONCE_BITS = std::min(n.
bits() - 2, PREF_NONCE_BITS);
294 MillerRabin_Test mr(n);
299 const size_t tests = miller_rabin_test_iterations(n.
bits(), level);
301 for(
size_t i = 0; i != tests; ++i)
304 while(nonce < 2 || nonce >= (n-1))
307 if(mr.is_witness(nonce))
const size_t PRIME_TABLE_SIZE
word word_at(size_t n) const
BigInt gcd(const BigInt &a, const BigInt &b)
std::invalid_argument Invalid_Argument
Fixed_Exponent_Power_Mod pow_mod
bool primality_test(const BigInt &n, RandomNumberGenerator &rng, size_t level)
RandomNumberGenerator * rng
void randomize(RandomNumberGenerator &rng, size_t bitsize=0)
void set_base(const BigInt &) const
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)
const u16bit BOTAN_DLL PRIMES[]
BigInt square(const BigInt &x) const
BigInt lcm(const BigInt &a, const BigInt &b)
void set_exponent(const BigInt &) const